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最小的值。。。。

　然后就可以开始暴力了。

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

 #include<iostream>

 #include<cstdio>

 using namespace std;

 inline long long max(long long a,long long b)

 {

     if(a>b)return a;

     else return b;

 }

 inline long long min(long long a,long long b)//mustwriteforlonglong!!!

 {

     if(a<b)return a;

     else return b;

 }

 inline long long qmax(long long a,long long b,long long c)

 {

     long long ma=max(a,b);

     return max(ma,c);

 }

 inline long long qmin(long long a,long long b,long long c,long long d)

 {

     long long mi=min(a,b);

     mi=min(mi,c);

     return min(mi,d);

 }

 long long a[],tot1,tot2,tot3,sum,k1,k2,par,minl;

 int main()

 {

 //    freopen("divide.in","r",stdin);

 //freopen("divide.out","w",stdout);

     int n;

     cin>>n;

     for(int i=;i<=n;i++)

     {

         scanf("%lld",&a[i]);

         sum+=a[i];

     }

     long long e=3LL;

     par=sum/e;

     for(int i=;i<=n;i++)

     {

         tot1+=a[i];

         if(tot1>=par)

         {

             k1=i;

             break;

         }

     }

     for(int i=n;i>=;i--)

     {

         tot2+=a[i];

         if(tot2>=par)

         {

             k2=i;

             break;

         }

     }

     tot3=sum-tot1-tot2;

     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]));

     cout<<minl;

 }

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

代码如下：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n;

 long long a[],sum[],ans;

 long long min(long long a,long b)

 {

     return a>b?b:a;

 }

 long long max(long long a,long b)

 {

     return a<b?b:a;

 }

 int main()

 {

     freopen("divide.in","r",stdin);

     freopen("divide.out","w",stdout);

     cin>>n;

     for (int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         sum[i]=sum[i-]+a[i];//前缀和

     }

     ans=sum[n];// "yournum+ll(LL)"

     for (int i=;i<=n;i++)

     {

         long long sa=sum[i-];

         int l=i+,r=n+;//l=i+1?? r=n+1??

         while (l<r-)//二分 l<r-1???

         {

             int mid=(l+r)>>;

             if (sum[mid-]-sa<=sum[n]-sum[mid-])//mid-1??

               l=mid;

             else r=mid;

         }

         long long sb=sum[l-]-sa,sc=sum[n]-sum[l-];//the ans may be the third one

         ans=min(ans,max(sa,max(sb,sc)));

         sb=sum[l]-sa;sc=sum[n]-sum[l];//the ans may be the second one

         ans=min(ans,max(sa,max(sb,sc)));

     }

     cout<<ans;

     return ;

 }

注意事项：

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

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

巴特西

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

LGTB 学分块

输入

输出

样例

解题报告

最新文章

热门文章