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、各种边界。/*还没弄懂*/