做题实录

 1 //二分+DP 
 2 #include<iostream>
 3 #include<algorithm>
 4 #define N 20010
 5 using namespace std;
 6 int n,ans,a[N],maxn[N],minn[N],l,r;
 7 bool dp(int x){
 8     maxn[1]=minn[1]=a[1];
 9     for(int i=2;i<=n;i++){
10         maxn[i]=min(a[i],a[1]-minn[i-1]);
11         minn[i]=max(0,a[i]-(x-a[i-1]-a[1]+maxn[i-1]));
12     }
13     if(!minn[n]) return 1;
14     else return 0;
15 }
16 int main()
17 {
18     ios::sync_with_stdio(false);        //cin加速 
19     cin>>n;
20     for(int i=1;i<=n;i++){
21         cin>>a[i];
22         if(i>=2) l=max(l,a[i]+a[i-1]);
23         if(i>=3) r=max(r,a[i]+a[i-1]+a[i-2]);
24     }
25     l=max(l,a[1]+a[n]);
26     r=max(max(r,a[n]+a[1]+a[2]),a[n-1]+a[n]+a[1]);
27     ans=r;
28     while(l<=r){
29         int mid=(l+r)>>1; 
30         if(!dp(mid)){
31             l=mid+1;
32         }
33         else {
34             ans=min(ans,mid);
35             r=mid-1;
36         }
37     }
38     cout<<ans;    
39     return 0;
40 }        //注意大括号 英汉相貌一模一样 
41 /*
42 //贪心(乱搞)
43 #include<iostream>
44 #include<cmath> 
45 #include<algorithm>
46 #define N 20010
47 using namespace std;
48 int n,ans,a[N],l;
49 double sum,nn;
50 int main()
51 {
52     ios::sync_with_stdio(false);        //cin加速 
53     cin>>n;
54     for(int i=1;i<=n;i++){
55         cin>>a[i];
56         if(i>=2) l=max(l,a[i]+a[i-1]);
57         sum+=a[i];
58     }
59     l=max(l,a[1]+a[n]);
60     nn=n;        //不可以sum*2/n,(n/2)自动向下取整 
61     cout<<max(l,(int)ceil(sum/(n/2)));        //ceil向上取整函数类型为double 
62     return 0;                                //floor 向下取整 
63 }
64 */