黑猫_琉璃 @ 2018-11-03 00:09:22
不好意思深夜打扰了。
这道题我的思路基本是暴力枚举,稍微加了一点点优化。结果提交上去之后发现WA了第2、3、7个点。请问是为什么呢?觉得自己的代码没有问题,可第二个测试点又“该测试点数据过大无法下载”。
求教大佬。
#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
#define INF INT_MAX
int n,k,num[1000005],maxn,minn = INF,cs,maxs[1000005],mins[1000005],len;
bool chgmin = false,chgmax = false;
int main(void){
//得到数字的数量和滑动窗口的大小
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
}
cs = n - k + 1;
for(int i=1;i<=k;i++){
if(num[i] > maxn){
maxn = num[i];
}
if(num[i] < minn){
minn = num[i];
}
}
//保存
len++;
maxs[len] = maxn;
mins[len] = minn;
//判断是否需要更换最小值/最大值
if(minn == num[1]){
chgmin = true;
}
if(maxn == num[1]){
chgmax = true;
}
for(int i=2;i<=cs;i++){
//得到最大值
if(!chgmax){
if(num[i+k-1] > maxn){
maxn = num[i+k-1];
}
}else{
//重置
maxn = 0;
//遍历之后的k个数
for(int j=i;j<=k+i-1;j++){
if(num[j] > maxn){
maxn = num[j];
}
}
}
//得到最小值
if(!chgmin){
if(num[i+k-1] < minn){
minn = num[i+k-1];
}
}else{
minn = INF;
for(int j=i;j<=k+i-1;j++){
if(num[j] < minn){
minn = num[j];
}
}
}
//保存
len++;
maxs[len] = maxn;
mins[len] = minn;
//重置
chgmax = chgmin = false;
//判断是否需要更换最大/最小值
if(minn == num[i]){
chgmin = true;
}
if(maxn == num[i]){
chgmax = true;
}
}
//输出
for(int i=1;i<=len;i++){
printf("%d ",mins[i]);
}
printf("\n");
for(int i=1;i<=len;i++){
printf("%d ",maxs[i]);
}
return 0;
}
by ez_lcw @ 2018-12-05 13:19:37
@黑猫_琉璃
by 黑猫_琉璃 @ 2018-12-08 11:50:28
@20181gdgzoi236_lc 感谢dalao,我已经AC了。(第一道绿题,想想都有点激动啊)
by ez_lcw @ 2018-12-08 17:57:27
不谢