二分答案方法、

不懂的戳上面、

codeforces 460C、

题意：给n个花的高度给你、然后有m天，w的长度、每天只可以浇一次水、浇水的是一个连续的区间长度为w、浇一次长度加1、求经过浇水后高度花的最大值、

思路：二分答案+贪心策略（检查答案可能性）、

PS：我在进行check的时候不会出现m天浇不完的情况、因为我在开始的时候就已经确定答案的区间了、二分到答案的最大可能值的时候m次必定会浇完、

 1 #include<cmath>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 using namespace std;
 8 const int qq=100005;
 9 int n,m,w;
10 int num[qq];
11 int ck[qq];
12 int vis[qq];
13 bool check(int x)
14 {
15     for(int i=0;i<n;++i){
16         ck[i]=num[i];
17         vis[i]=0;
18     }
19     int mark=0;
20     int can=m;
21 //    printf("%d
",x);
22     for(int i=0;i<n;++i){
23         ck[i]+=mark;//注意这之间的先后顺序、得先加上mark 
24         if(ck[i]<x){     
25             int plus=x-ck[i];
26             if(can-plus<0)    return false;
27             mark+=plus;            //当前需要加的值、 
28             can-=plus;
29             vis[i+w-1]=plus;    //所要加的值的断点、 
30         }
31         if(vis[i]!=0)    mark-=vis[i];
32     }
33     return true;
34 }
35 int main()
36 {
37     scanf("%d%d%d",&n,&m,&w);
38     int minx=1e9+1;
39     int maxn=0;
40     for(int i=0;i<n;++i){
41         scanf("%d",&num[i]);
42         minx=min(minx,num[i]);
43         maxn=max(maxn,num[i]);
44     }
45     int l,r,mid;
46     l=0;r=maxn+m;    //答案的最小和最大范围、 
47     int ans=0;
48     while(l<=r){
49         mid=(l+r)>>1;
50         if(check(mid))    ans=mid,l=mid+1;
51         else            r=mid-1;
52     }
53     printf("%d
",ans);
54     return 0;
55 }

POJ 3104

题意：给你n件衣服所含的水分、然后给你一个数值k代表烘干机一次对一件衣服能吹干的水分、（在烘干机烘干一件衣服的时候其他衣服就是自然干一分钟减一水分）

思路：典型的二分答案、、

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<iostream>
 4 using namespace std;
 5 const int qq=100010;
 6 int n;
 7 int water[qq];
 8 int k;        //烘干机一次烘掉的水分、 
 9 int t=-1;    //最终答案、所有衣服干完的最少时间 
10 int maxn=-1;    //所有衣服干完的最长用时、 
11 bool check(int mid)
12 {
13     //若某件衣服水分ai<mid 可以自然风干、否则需要烘、
14     //假设这件衣服风干用时t1，烘烤用时t2
15     //(1)t1+t2>=mid;
16     //(2)t1+k*t2>=water[i]
17     //所以 t2>=(water[i]-mid)/(k-1) 
18     double rad=0;    //使用烘干机的总时间、 
19     for(int i=0;i<n;++i)
20         if(water[i]>mid)
21             rad+=ceil((double(water[i]-mid))/(double)(k-1));
22     if(rad<=mid)    return true;
23     else    return false;
24 }
25 void solve()
26 {
27     int l=0;
28     int r=maxn;
29     int mid=(l+r)>>1;
30     while(l<=r){
31         if(check(mid)==true){
32             if(check(mid-1)==false){
33                 t=mid;
34                 return;
35             }
36             r=mid-1;
37         }
38         else    l=mid+1;
39         mid=(l+r)>>1;
40     }
41 }
42 int main()
43 {
44     scanf("%d",&n);
45     int res=0;
46     for(int i=0;i<n;++i){
47         scanf("%d",&water[i]);
48         maxn=maxn>water[i]?maxn:water[i];
49     }
50     scanf("%d",&k);
51     solve();
52     printf("%d
",t);
53     return 0;
54 }