本人对于二分极度不擅长，于是每次代码都bug百出。怪我喽
在写二分模板时时经常分不清二分是叉叉勾勾还是勾勾叉叉形，加之有时check函数的返回值又写错。。。人生无望啊～
题目链接戳标题↑
分析：
一道典型的二分答案题，所有可能的答案，满足勾勾叉叉形（我们老师说的，大概就是说：要求出的最小距离越短，则能拿出的瓶盖越多，越可能能满足题目要求）。
伪代码(以及我的花式错误)
就只写写本题目二分部分的啦
大概是酱紫的↓（正确）：
1
2
3
4
5
6
|
左指针<右指针时重复进行:
平均数=(左指针+右指针+1)/2
若距离为平均数时满足题意:
左指针等于平均数
否则：
右指针等于平均数-1
|
对错分界线
典型错误作死示范（亲身经历）：
示例1:
1
2
3
4
5
6
|
左指针<右指针时重复进行:
平均数=(左指针+右指针)/2
若距离为平均数时满足题意:
左指针等于平均数+1
否则：
右指针等于平均数
|
样例会输出三，这个就不说为什么了，你知道的
示例2:
1
2
3
4
5
6
|
左指针<右指针时重复进行:
平均数=(左指针+右指针)/2
若距离为平均数时满足题意:
左指针等于平均数
否则：
右指针等于平均数-1
|
不加一害死人啊！
这样的代码样例将是正确的，但是在多半的数据点会发生死循环。
比如当左指针=3，右指针=4，且距离为三的时候满足条件就会出现这样的悲剧：
全部代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 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;
}
|
总结