农田灌溉 AcWing"/>
农田灌溉 AcWing
文章目录
题目描述
一、初始代码
二、改正后
三、借鉴大佬后
总结
来练练
题目描述
/
一、初始代码
没什么技巧,纯纯的模拟
又臭又长不说,还有很多的bug,改了好久才全部通过,😔,
#include<bits/stdc++.h>
using namespace std;
int check(int *a,int n);
int main(){int T,i,j,n,k;cin>>T;for(j=0;j<T;j++){cin>>n>>k;if(n==1){cout<<1<<endl;return 0;}//bug1.该死的惯性思维,应该是continue的,呜呜else if(n==k){cout<<1<<endl;return 0;}else {int a[n+2],x,cnt=1;//下标从1开始memset(a,0,sizeof(int)*(n+2));//初始化函数,好用的很!for(i=0;i<k;i++){cin>>x;a[x]=1;}//洒水器的农田赋值1do{cnt++;for(i=1;i<=n;i++){if(a[i]==cnt-1){if(i-1>=1)a[i-1]=cnt;//bug2.数据考虑不全面,当洒水器连在一起时,数据会被覆盖掉if(i+1<=n)a[i+1]=cnt; } } }while(check(a,n)==0);cout<<cnt;}}return 0;
}
int check(int *a,int n){//判断是否所有的农田都被灌溉int i;for(i=1;i<=n;i++)if(!a[i])return 0;return 1;
}
二、改正后
#include<bits/stdc++.h>
using namespace std;
int check(int *a,int size);
int main(){int T,i,j,n,k,x;cin>>T;//cout<<T<<endl;for(j=0;j<T;j++){cin>>n>>k;if(n==k){for(i=0;i<k;i++){cin>>x;}cout<<1<<endl;continue;}else if(n==1){for(i=0;i<k;i++){cin>>x;}cout<<1<<endl;continue;}else {int a[n+2],cnt=1;//下标从1开始memset(a,0,sizeof(int)*(n+2));for(i=0;i<k;i++){cin>>x;a[x]=1;}do{++cnt;for(i=1;i<=n;i++){if(a[i]==cnt-1){if(i-1>=1&&a[i-1]!=cnt-1)a[i-1]=cnt;if(i+1<=n&&a[i+1]!=cnt-1)a[i+1]=cnt; } } }while(check(a,n)==0);cout<<cnt<<endl;}}return 0;
}
int check(int *a,int size){int i;for(i=1;i<=size;i++)if(a[i]==0)return 0;return 1;//&&a[i]>cnt)
}
改了好久才全部通过,😔
三、借鉴大佬后
#include<bits/stdc++.h>//万能头文件,巨好用!!!
using namespace std;//一定要有,不然会编译出错!!
int main(){int T;cin>>T;while(T--){int n,k,i,cnt;cin>>n>>k;int a[210];for(i=1;i<=k;i++)cin>>a[i];//下标从1起cnt=max(a[1],n-a[k]+1);//找头尾处 离洒水器最远的田地for(i=1;i<k;i++)cnt=max(cnt,(a[i+1]+a[i])/2-a[i]+1);//找中间 离洒水器最远的田地 也就是算2个洒水器中位数下标cout<<cnt<<endl;return 0; }
}
短小,思路清晰,
看大佬码字真的如沐春风,五体投地!!
总结
1.一定要记住自己犯过的错
2.数据测试不过,就手算一遍,别怀疑电脑有问题,是你有问题,没发现低级的错误!!!!
一定要手算,光用眼睛看是很难发现的!!
来练练手
蓝桥杯灌溉
注意这道题给的测试用例不全,虽然pass,也可能不对,还是要自己找数据验证
别忘了 测试样例要多元化!!
更多推荐
农田灌溉 AcWing
发布评论