admin 管理员组文章数量: 887021
windo
windo
题目描述：
给你一个长度为 N 的数组，一个长为 K 的滑动的窗体从最左移至最右端，
你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
Windo position Min value Maxvalue
[ 1 3 -1 ] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7你的任务是找出窗口在各位置时的 max value,min value.
输入格式：
第 1 行n,k,
第 2 行为长度为 n 的数组
输出格式：
2 行，
第 1 行每个位置的 min value,
第 2 行每个位置的 max value
样例输入：
8 3
1 3 -1 -3 5 3 6 7
样例输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围：
20%： n<=500;
50%: n<=100000;
100%: n<=1000000;
k<=n;
时间限制：
三秒（表示程序两秒就能过）
嗯…当我做这道题的时候，lzh学长告诉我这道题是要用单调队列做的…当时还没有学单调队列。然而在于我不信邪，偏要用数组做。//不能多次测试的时候别学我
嗯...偏偏在于我真的试出来了，最开始没有优化的时候过了五组。优化了一下，九组，当时耗时还是3秒，最后的优化终于过而且不到两秒。
嗯...前面废话请自行省略...我只是过来表达一下激动的心情。好了下面上代码：
最初：
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int nn[1000100],mn[1000100]={},mx[1000100]={};
int main()
{/*freopen("00.in","r",stdin);freopen("00.out","w",stdout);*/int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>nn[i];for(int i=1;i<=n-k+1;i++){int maxx=-10000000,minn=10000000;for(int j=i;j<i+k;j++){if(nn[j]>maxx)maxx=nn[j];if(nn[j]<minn)minn=nn[j];}mn[i]=minn; mx[i]=maxx;}for(int i=1;i<=n-k+1;i++) cout<<mn[i]<<' ';cout<<endl;for(int i=1;i<=n-k+1;i++) cout<<mx[i]<<' ';return 0;
}
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int nn[1000100],mn[1000100]={},mx[1000100]={};
int main()
{/*freopen("00.in","r",stdin);freopen("00.out","w",stdout);*/int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>nn[i];int maxx=-10000000,minn=10000000;for(int i=1;i<=k;i++){if(nn[i]>maxx)maxx=nn[i];if(nn[i]<minn)minn=nn[i];}mn[1]=minn; mx[1]=maxx;for(int i=2;i<=n-k+1;i++){if((maxx==nn[i-1])||(minn==nn[i-1])){maxx=-10000000,minn=10000000;if(maxx<nn[i-1+k]) maxx=nn[i-1+k];if(minn>nn[i-1+k]) minn=nn[i-1+k];for(int j=i;j<i+k;j++){if(nn[j]>maxx)maxx=nn[j];if(nn[j]<minn)minn=nn[j];}}else{if(maxx<nn[i-1+k]) maxx=nn[i-1+k];if(minn>nn[i-1+k]) minn=nn[i-1+k];}mn[i]=minn; mx[i]=maxx;}for(int i=1;i<=n-k+1;i++) cout<<mn[i]<<' ';cout<<endl;for(int i=1;i<=n-k+1;i++) cout<<mx[i]<<' ';return 0;
}
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int nn[1000100],mn[1000100]={},mx[1000100]={};
int main()
{/*freopen("00.in","r",stdin);freopen("00.out","w",stdout);*/std::ios::sync_with_stdio(false);int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>nn[i];int maxx=-10000000,minn=10000000;for(int i=1;i<=k;i++){if(nn[i]>maxx)maxx=nn[i];if(nn[i]<minn)minn=nn[i];}mn[1]=minn; mx[1]=maxx;for(int i=2;i<=n-k+1;i++){if((maxx==nn[i-1])||(minn==nn[i-1])){maxx=-10000000,minn=10000000;if(maxx<nn[i-1+k]) maxx=nn[i-1+k];if(minn>nn[i-1+k]) minn=nn[i-1+k];for(int j=i;j<i+k;j++){if(nn[j]>maxx)maxx=nn[j];if(nn[j]<minn)minn=nn[j];}}else{if(maxx<nn[i-1+k]) maxx=nn[i-1+k];if(minn>nn[i-1+k]) minn=nn[i-1+k];}mn[i]=minn; mx[i]=maxx;}for(int i=1;i<=n-k+1;i++) cout<<mn[i]<<' ';cout<<endl;for(int i=1;i<=n-k+1;i++) cout<<mx[i]<<' ';return 0;
}
其实看了会发现第二次与最后一次只差了一点，强烈推荐一个好用的东西：
std::ios::sync_with_stdio(false);可以去百度一下这是什么。效率特别高，别问我为什么，我也不知道。
好了接下来来说一下我的思路，最初始的，也就是搜索，一次一次搜。
改过之后的也就是先判断每次去掉的是不是最大或最小，不是什么都好说，看新增进来的有没有比最大的大或者比最小的小。没有的话还是在数组里存原来的最大最小。有的话那也就是赋值再存。
但是当去掉的是最大或者最小的时候，再查找一遍（这里应该是可以优化的，但是怪我有点懒）。
最后输出。就这样。
本文标签： windo
版权声明：本文标题：windo 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687769607h139219.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论