ABC263
VP
| score | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 105:02 | 0:24 | 4:11 | 15:03 | 38:49 | 85:02 | ||
| +4 | +1 | +1 | +2 |
rk:\(316th\)
perf:\(\color{Gold}{2012}\)
A、B
忽略。
C
就是记一下 next_permutation 这个函数。
或者爆搜也行。
void work(){
cin>>n>>m;vi f;
L(i,1,n) f.pb(0);
L(i,1,m-n) f.pb(1);
do{
L(i,0,m-1) if(!f[i])
cout<<i+1<<" ";
cout<<'\n';
}while(next_permutation(all(f)));
}
D
稍微分类讨论一下，把问题转化成更为更加可解的情况。
- 如果整个数组 \(a\) 都被覆盖
此时答案显然是 \(\min(L,R) \cdot n\)。
- 如果数组不是完全覆盖
中间必然有一段 \(\left[ l,r \right]\) 没有被改变。
考虑一个前缀和数组 \(s_i = \sum_{j=1}^i a_j\)，此时的答案为 $$s_r -s_{l-1}+R \times (n-r) +L \times (l-1)$$
所以枚举左端点 \(l\) 和后缀最小和 \(s_{l} + R \times (n-r)\) 并更新答案即可。
void work(){
cin>>n>>x>>y;
L(i,1,n) cin>>a[i],s[i]=a[i]+s[i-1];
R(i,n,0){
sum=min(sum,s[i]+y*(n-i));
ans=min(ans,x*i-s[i]+sum);
}cout<<ans;
}
