Codeforces Round #956 (Div. 2)
C.Have Your Cake and Eat It Too
题目大意：
有长度为
n
n
n的数组
a
,
b
,
c
a,b,c
a,b,c，三个数组的和相同，把
n
n
n分为三段非空连续段
[
l
a
,
r
a
]
,
[
l
b
,
r
b
]
,
[
l
c
,
r
c
]
[l_a,r_a],[l_b,r_b],[l_c,r_c]
[la,ra],[lb,rb],[lc,rc],互不重合。
保证
∑
i
=
l
a
r
a
a
i
,
∑
i
=
l
b
r
b
b
i
,
∑
i
=
l
c
r
c
c
i
>
=
k
\sum_{i=l_a}^{r_a}a_i,\sum_{i=l_b}^{r_b}b_i,\sum_{i=l_c}^{r_c}c_i >=k
∑i=laraai,∑i=lbrbbi,∑i=lcrcci>=k
k
k
k是大于等于
∑
i
=
1
n
a
i
n
\frac{\sum_{i=1}^{n}a_i}{n}
n∑i=1nai的整数
输出
l
a
,
r
a
,
l
b
,
r
b
,
l
c
,
r
c
l_a,r_a,l_b,r_b,l_c,r_c
la,ra,lb,rb,lc,rc,如果无法分就输出-1
解题思路：
考虑三种可能性
1.
[
l
a
,
r
a
]
[l_a,r_a]
[la,ra]在1-n左边，就是
a
b
c
/
a
c
b
abc/acb
abc/acb
2.
[
l
a
,
r
a
]
[l_a,r_a]
[la,ra]在1-n右边，就是
b
c
a
/
c
b
a
bca/cba
bca/cba
3.
[
l
a
,
r
a
]
[l_a,r_a]
[la,ra]在1-n中间，就是
b
a
c
/
c
a
b
bac/cab
bac/cab
先前缀和一遍，方便计算子数组的和
可能性1：
遍历
l
a
=
1
l_a=1
la=1,遍历1-n，找到最小的
r
a
r_a
ra,然后在
[
r
a
+
1
,
n
]
[r_a+1,n]
[ra+1,n]，遍历每个位置，判断一下
b
b
b和
c
c
c的子数组和是否满足
>
=
k
>=k
>=k
for(int i=1;i<n-1;i++){
if(a[i]>=k){
s1=i;
break;
}
}
for(int i=s1+1;i<n;i++){
if(b[i]-b[s1]>=k&&c[n]-c[i]>=k){
cout<<1<<' '<<s1<<' '<<s1+1<<' '<<i<<' '<<i+1<<' '<<n<<'\n';
return ;
}
if(c[i]-c[s1]>=k&&b[n]-b[i]>=k){
cout<<1<<' '<<s1<<' '<<i+1<<' '<<n<<' '<<s1+1<<' '<<i<<'\n';
return ;
}
}
可能性1：
遍历
r
a
=
n
r_a=n
ra=n,遍历n-1，找到最大的
l
a
l_a
la,然后在
[
1
,
l
a
−
1
]
[1,l_a-1]
[1,la−1]，遍历每个位置，判断一下
b
b
b和
c
c
c的子数组和是否满足
>
=
k
>=k
>=k
for(int i=n;i>2;i--){
if(a[n]-a[i-1]>=k){
s1=i;
break;
}
}
for(int i=1;i<s1-1;i++){
if(b[i]>=k&&c[s1-1]-c[i]>=k){
cout<<s1<<' '<<n<<' '<<1<<' '<<i<<' '<<i+1<<' '<<s1-1<<'\n';
return ;
}
if(c[i]>=k&&b[s1-1]-b[i]>=k){
cout<<s1<<' '<<n<<' '<<i+1<<' '<<s1-1<<' '<<1<<' '<<i<<'\n';
return ;
}
}
可能性3：
遍历2-(n-1),枚举每个节点为
l
a
l_a
la，二分找满足条件的最小
r
a
r_a
ra，再判断两边的
b
b
b和
c
c
c的子数组和是否满足
>
=
k
>=k
>=k
int s1,s2,s3,l,r,mid;
for(int i=2;i<n;i++){
l=i,r=n;
while(l<r){
mid=(l+r)/2;
if(a[mid]-a[i-1]<k)l=mid+1;
else r=mid;
}
if(a[l]-a[i-1]>=k){
if(b[i-1]>=k&&c[n]-c[l]>=k){
cout<<i<<' '<<l<<' '<<1<<' '<<i-1<<' '<<l+1<<' '<<n<<'\n';
return ;
}
if(c[i-1]>=k&&b[n]-b[l]>=k){
cout<<i<<' '<<l<<' '<<l+1<<' '<<n<<' '<<1<<' '<<i-1<<'\n';
return ;
}
}
}
最后都没有满足的就输出-1
完整代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
int a[N],b[N],c[N];
void solve()
{
int n,sum=0;
cin>>n;
a[0]=0,b[0]=0,c[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
sum+=a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
b[i]+=b[i-1];
}
for(int i=1;i<=n;i++){
cin>>c[i];
c[i]+=c[i-1];
}
int k=a[n]/3;
if(a[n]%3)k++;
int s1,s2,s3,l,r,mid;
for(int i=2;i<n;i++){
l=i,r=n;
while(l<r){
mid=(l+r)/2;
if(a[mid]-a[i-1]<k)l=mid+1;
else r=mid;
}
if(a[l]-a[i-1]>=k){
if(b[i-1]>=k&&c[n]-c[l]>=k){
cout<<i<<' '<<l<<' '<<1<<' '<<i-1<<' '<<l+1<<' '<<n<<'\n';
return ;
}
if(c[i-1]>=k&&b[n]-b[l]>=k){
cout<<i<<' '<<l<<' '<<l+1<<' '<<n<<' '<<1<<' '<<i-1<<'\n';
return ;
}
}
}
for(int i=1;i<n-1;i++){
if(a[i]>=k){
s1=i;
break;
}
}
for(int i=s1+1;i<n;i++){
if(b[i]-b[s1]>=k&&c[n]-c[i]>=k){
cout<<1<<' '<<s1<<' '<<s1+1<<' '<<i<<' '<<i+1<<' '<<n<<'\n';
return ;
}
if(c[i]-c[s1]>=k&&b[n]-b[i]>=k){
cout<<1<<' '<<s1<<' '<<i+1<<' '<<n<<' '<<s1+1<<' '<<i<<'\n';
return ;
}
}
for(int i=n;i>2;i--){
if(a[n]-a[i-1]>=k){
s1=i;
break;
}
}
for(int i=1;i<s1-1;i++){
if(b[i]>=k&&c[s1-1]-c[i]>=k){
cout<<s1<<' '<<n<<' '<<1<<' '<<i<<' '<<i+1<<' '<<s1-1<<'\n';
return ;
}
if(c[i]>=k&&b[s1-1]-b[i]>=k){
cout<<s1<<' '<<n<<' '<<i+1<<' '<<s1-1<<' '<<1<<' '<<i<<'\n';
return ;
}
}
cout<<"-1\n";
}
signed main()
{
int T;
cin>>T;
while(T--)
{;
solve();
}
return 0;
}