本人对于二分极度不擅长,于是每次代码都bug百出。怪我喽
在写二分模板时时经常分不清二分是叉叉勾勾
还是勾勾叉叉
形,加之有时check
函数的返回值又写错。。。人生无望啊~
P1316 丢瓶盖
题目链接戳标题↑
分析:
一道典型的二分答案题,所有可能的答案,满足勾勾叉叉
形(我们老师说的,大概就是说:要求出的最小距离越短,则能拿出的瓶盖越多,越可能能满足题目要求)。
伪代码(以及我的花式错误)
就只写写本题目二分部分的啦
大概是酱紫的↓(正确):
左指针<右指针时重复进行:
平均数=(左指针+右指针+1)/2
若距离为平均数时满足题意:
左指针等于平均数
否则:
右指针等于平均数-1
对错分界线
典型错误作死示范(亲身经历):
示例1:
左指针<右指针时重复进行:
平均数=(左指针+右指针)/2
若距离为平均数时满足题意:
左指针等于平均数+1
否则:
右指针等于平均数
样例会输出三,这个就不说为什么了,你知道的
示例2:
左指针<右指针时重复进行:
平均数=(左指针+右指针)/2
若距离为平均数时满足题意:
左指针等于平均数
否则:
右指针等于平均数-1
不加一害死人啊!
这样的代码样例将是正确的,但是在多半的数据点会发生死循环。
比如当左指针=3,右指针=4,且距离为三的时候满足条件就会出现这样的悲剧:
无限循环:
左指针=左指针
全部代码:
# include <cstdio>
# include <algorithm>
using namespace std;
const int NR=100005;
//一大堆定义,包括二分中要用的
int n,m,arr[NR],l=0,r,mid,va;
inline bool check(int dis){
int last_i=0,cnt=1;
for(int i=1;i<n;i++)
if(arr[i]-arr[last_i]>=dis){
cnt++;
last_i=i;
}
return cnt>=m;
}
int main(){
//读入没得说
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",arr+i);
sort(arr,arr+n);
//题目中没说输入队列一定有序
r=arr[n-1];
//r赋值为最远的瓶盖
while(l<r){
mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d",l);
return 0;
}
总结
- 要背好二分模板
- 保持清醒思考问题!
作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接
阅读量: