题解：CF1271F Divide The Students
yingkeqian9217
·
·
题解
提供一种好写的线性做法。
注意到单个和全部是好做的，而两个可以转化为全局加单点减同一个数，于是转化为前两者。枚举总共加的值，计算出所有第二类的取值范围相加检查即可，时间复杂度 O(n)。
对边界略加分讨应该可以做到 O(1)。
```cpp
#include<bits/stdc++.h>
using namespace std;
int l[3],r[3],s[8],P[8]={0,7,3,5,1,6,2,4},a[8],L[8],R[8];
void print(int k){
int res=k;
for(int i=0;i<3;i++) res-=L[i];
for(int i=0;i<3;i++){
res-=(a[(1<<i)^7]=min(res,R[i]-L[i]));
a[(1<<i)^7]+=L[i];
a[1<<i]=max(0,l[i]-k+a[(1<<i)^7]);
}
a[7]=res;
for(int i=1;i<8;i++) printf("%d ",a[P[i]]);printf("\n");
}
inline void solve(){
int sum=0;
for(int i=0;i<3;i++) scanf("%d",&r[i]);
for(int i=0;i<3;i++) scanf("%d",&l[i]);
for(int i=1;i<8;i++) scanf("%d",&s[P[i]]),sum+=(__builtin_popcount(P[i])>1)*s[P[i]];
for(int i=0;i<3;i++){
int sum=0;
for(int j=(1<<i);j<8;j=((j+1)|(1<<i))) sum+=s[j];
l[i]=max(0,sum-l[i]);
if(l[i]>r[i]) return puts("-1"),void();
}
for(int i=0;i<=sum;i++){
int fl=1,suml=0,sumr=s[7];
for(int j=0;j<3;j++){
L[j]=max(0,-(r[j]-i)),R[j]=min(s[(1<<j)^7],s[1<<j]-(l[j]-i));
if(L[j]>R[j]) fl=0;
suml+=L[j],sumr+=R[j];
}
fl&=(suml<=i&&i<=sumr);
if(!fl) continue;
return print(i);
}
puts("-1");
}
signed main(){
signed T=1;
scanf("%d",&T);
while(T--) solve();
return 0;
}
```