洛谷 P1824 【进击的奶牛】

我写了个set版本的O_O

二分的细节方面很让人头疼，我用”//zy“(注意)标注了一些细节O_O

#include<cstdio>
#include<iostream> #include<iterator> #include<set> #include<algorithm> using namespace std; int n,c; set<int> oxro; set<int>::iterator it=oxro.end(); bool check(int dis){ int last=*oxro.begin(),niu=0;//zy for(it=oxro.begin(),it++;it!=oxro.end();it++){//zy if(*it-last>=dis){ niu++; last=*it; } if(niu>=c)return 1; } if(niu+1<c)return 0;//zy//zy return 1; } int main(){ scanf("%d%d",&n,&c); for(int i=1;i<=n;i++){ int room; scanf("%d",&room); oxro.insert(room); } int l=1,r=*(--it)-*oxro.begin();//zy while(l<=r){//zy int mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid-1; } printf("%d\n",r);//zy }

细节方面也可以这样写,也通过了:

#include<cstdio>
#include<iostream> #include<iterator> #include<set> #include<algorithm> using namespace std; int n,c; set<int> oxro; set<int>::iterator it=oxro.end(); bool check(int dis){ int last=*oxro.begin(),niu=1;//niu=1注意 for(it=oxro.begin(),it++;it!=oxro.end();it++){//zy if(*it-last>=dis){ niu++; last=*it; } if(niu>=c)return 1; } return 0; } int main(){ scanf("%d%d",&n,&c); for(int i=1;i<=n;i++){ int room; scanf("%d",&room); oxro.insert(room); } int l=0,r=*(--it)-*oxro.begin()+1;//zy int mid; while(l<=r){//zy mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid-1; } printf("%d\n",r);//zy }

解析

part1 什么是二分，本题怎么用(萌新模板)

    //不久前,本蒟蒻终于明白了:二分就是暴力，优化的暴力O_O
    //注意:二分的有些细节问题，例如循环条件到底要不要加'=',一定要编数据多调试!!!(其实对于本蒟蒻，往往会因为这些点磨叽很久...多多尝试吧!!!)
    //对于"最大值的最小值","最小值的最大值"之类的题一般都是用二分。
    //例如本题为"最小值的最大值"，通过"二分"的方式来枚举"最大值"的可能值。(如果枚举出的mid符合条件，那我们再搜一搜有没有比mid大的值也符合条件O_O) 

part2 如何判断枚举出的"最大值"是否符合条件(二分题关键)

    //我看了看楼下的题解，主要的方法有两种：
    //1.保证距离与牛栏数，看能否放下c头牛 (我用的是这种)
    //2.保证距离与牛数，看需要多少牛栏 
    //注意:某些东西在循环里return貌似是有那么一点点快O_O 

2018/11/14更新：

1.set的版本在windows下的oj中不一定能过，有可能会超时。
2.有一个点必须要注意：最后要输出r,因为r在r、l、mid中理论上是最大的，否则大部分WA