一道裸的二分答案
如果不会分治的去找dalao吧,本蒟蒻只会二分
不知道二分答案的看这里
这位dalao解释的很详细其实只是随便找了一个
那里面貌似也有这个题的题解,但我还是要写(才不是应付老师)
关于二分答案我也稍稍解释一下,
假设你需要50块钱(逃课泡吧)
你:妈妈我要50块钱用来学习
第一种情况(正常情况)
妈妈:给你100块,好好学;
第二种情况
妈妈:给你30块,没那么多了
如果是第一种情况,那么你肯定接受,因为你可以有更长时间泡吧
但是如果是第二种情况呢?
30块并不能满足你的需求,这样的话你一定没等到时候你又得去学校
也就是说,你需要50元,妈妈只能给你50元以上才可以满足要求,但她不能给你太多防止你干坏事
那么这就是重点了,如果你不说你需要50元,妈妈并不知道,但妈妈可以问给你XX元可以吗
那么妈妈就可以找一个范围,她估摸你不会超过要300元泡吧
她就先猜150元,你说可以,那就说明你需要的真正钱数在0到150元之间,也就是说如果妈妈猜出一个钱数(150)可以满足要求;
那么比150多肯定也能满足要求,但149(或更低)不一定
这就是二分答案的适用范围,答案具有单调性(即上一行的解释)
如果知道这个那么再看这个题就简单多啦.
代码奉上
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<stack> #include<queue> #include<iostream> using namespace std; int n,m,l,aa; int a[50001]; bool dd(int x) { int kkk=l;//kkk表示还可以移动多少石头 int c,b=a[0];//c代表当前石头,b表示上一个(未搬走)的石头 for(int i=1; i<=m+1; i++) {//起点终点都要算上 c=a[i]; aa=c-b; if(aa>=x) {//符合条件更新上一个点的坐标 b=c; } else {//否则搬走 if(kkk==0) return 0; kkk--; } } return 1; } void dg(int t,int w) {//二分 if(t == w||t==w-1) {//二分边界 cout<<t; return ; } int mid = (t+w)/2; bool bb=dd(mid); if(bb == 0)//如果150块不行 dg(t,mid);//就从150到300找 else dg(mid,w);//行的话就从0到150找 } int main() { // freopen("stone9.in","r",stdin); // freopen("stone.out","w",stdout); scanf("%d%d%d",&n,&m,&l); int zd=0,zx=999999999; for(int i=1; i<=m; i++) { scanf("%d",&a[i]); aa=a[i]-a[i-1]; if(aa>zd)//找最大和最小 zd=aa; if(aa<zx) zx=aa; } a[m+1] = n;//算上终点 aa=a[m+1]-a[m]; if(aa>zd) zd=aa; if(aa<zx) zx=aa; int i; dg(zx,zd); return 0; }