神奇的NOIP模拟赛 T2 LGTB 学分块

LGTB 学分块

LGTB 最近在学分块，但是他太菜了，分的块数量太多他就混乱了，所以只能分成3 块
今天他得到了一个数组，他突然也想把它分块，他想知道，把这个数组分成3 块，块可以为空。假设3 块各
自的和中的最大值最小
请输出分完之后3 块中的最大值

输入

输入第一行包含一个整数n 代表数组大小
接下来n 个整数a1, a2, ..., an，代表数组
对于40% 的数据，1 n 10
对于70% 的数据，1 n 103
对于100% 的数据，1 n 105, 1 ai 107

输出

输出包含1 个整数，代表分块完成后3 块中的最大值

样例

样例输入
10
2 5 1 4 7 3 6 2 5 1

样例输出
14

解题报告

　　拿到这道题被“假设3 块各自的和中的最大值最小” 这句话给弄懵B 了......足足懵了半个小时，最后在同学的帮助下理解了。就是有很多种取块的方法，每一个方法取得值为各个块和的最大值sum，然后找出这么多取法中sum最小的值。。。。

　然后就可以开始暴力了。

　　还有一种求平均值的方法；

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 inline long long max(long long a,long long b)
 5 {
 6     if(a>b)return a;
 7     else return b;
 8 }
 9 inline long long min(long long a,long long b)//mustwriteforlonglong!!!
10 {
11     if(a<b)return a;
12     else return b;
13 }
14 inline long long qmax(long long a,long long b,long long c)
15 {
16     long long ma=max(a,b);
17     return max(ma,c);
18 }
19 inline long long qmin(long long a,long long b,long long c,long long d)
20 {
21     long long mi=min(a,b);
22     mi=min(mi,c);
23     return min(mi,d);
24 }
25 long long a[100005],tot1,tot2,tot3,sum,k1,k2,par,minl;
26 int main()
27 {
28 //    freopen("divide.in","r",stdin);
29 //freopen("divide.out","w",stdout);
30     int n;
31     cin>>n;
32     for(int i=1;i<=n;i++)
33     {
34         scanf("%lld",&a[i]);
35         sum+=a[i];
36     }
37     long long e=3LL;
38     par=sum/e;
39     for(int i=1;i<=n;i++)
40     {
41         tot1+=a[i];
42         if(tot1>=par)
43         {
44             k1=i;
45             break;
46         }
47     }
48     for(int i=n;i>=1;i--)
49     {
50         tot2+=a[i];
51         if(tot2>=par)
52         {
53             k2=i;
54             break;
55         }
56     }
57     tot3=sum-tot1-tot2;
58     minl=qmin(qmax(tot3,tot1,tot2),qmax(tot3+a[k1],tot1-a[k1],tot2),qmax(tot3+a[k2],tot1,tot2-a[k2]),qmax(tot3+a[k1]+a[k2],tot1-a[k1],tot2-a[k2]));
59     cout<<minl;
60 }

　　但其实正解是只枚举第一条边，然后对剩下的部分二分查找。记录比较最大值和最小值。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n;
 5 long long a[100005],sum[100005],ans;
 6 long long min(long long a,long b)
 7 {
 8     return a>b?b:a;
 9 }
10 long long max(long long a,long b)
11 {
12     return a<b?b:a;
13 }
14 int main()
15 {
16     freopen("divide.in","r",stdin);
17     freopen("divide.out","w",stdout);
18     cin>>n;
19     for (int i=1;i<=n;i++)
20     {
21         scanf("%d",&a[i]);
22         sum[i]=sum[i-1]+a[i];//前缀和 
23     }
24     ans=sum[n];// "yournum+ll(LL)"
25     for (int i=1;i<=n;i++)
26     {
27         long long sa=sum[i-1];
28         int l=i+1,r=n+1;//l=i+1?? r=n+1??
29         while (l<r-1)//二分 l<r-1???
30         {
31             int mid=(l+r)>>1;
32             if (sum[mid-1]-sa<=sum[n]-sum[mid-1])//mid-1??
33               l=mid;
34             else r=mid;
35         }
36         long long sb=sum[l-1]-sa,sc=sum[n]-sum[l-1];//the ans may be the third one
37         ans=min(ans,max(sa,max(sb,sc)));
38         sb=sum[l]-sa;sc=sum[n]-sum[l];//the ans may be the second one 
39         ans=min(ans,max(sa,max(sb,sc)));
40     }
41     cout<<ans;
42     return 0;
43 }

注意事项：

　　1、对long long 赋最大值要 long long x=12346789LL(或小写) ；

　　2、各种边界。/*还没弄懂*/