和小哥哥一起刷洛谷(9)

二分答案

Posted by ethan-zhou on March 5, 2019

本人对于二分极度不擅长,于是每次代码都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
本文为作者原创,转载请注明出处:本文链接