url:Problem – C – Codeforces
题意:
给n个数字和一个m
给一个操作:每次使得其中一个下标的数字 *= -1
要求最后在所有前缀和中前m个数字是最小的
思路:
在所有前缀和中分为三类,一类是在m前面的前缀和,一类是在m后面的前缀和,一类就是m本身
先考虑在m前面的前缀和
如何让在m前面的前缀和全部都>=m前缀和?
直接反过来考虑,从m开始向前面累加,如果累加的值>0了,代表需要操作一次了
因为如果累加值>0了,前面的一个前缀和直接不加这后面的一坨即可 < m前缀和
关于这个思路怎么来的
我借鉴了一下ygg的思路
k为其他前缀和的下标
a[1,k] >= a[1,m] => a[1,k] >= a[1,k] + a[k + 1,m]
所以能得到 a[k + 1,m] <= 0
又因为k >= 1,所以可以得到
任意的 i∈[2,m] 都有a[i,m] <= 0
所以要维护这个性质,就用上面的逆序处理即可
再考虑m后面的前缀和
跟前面的思路类似,对于i∈[m + 1,n]维护a[m + 1,i] >= 0即可
然后就是怎么去实现操作次数最小
直接贪心即可:每次需要操作时从已经遍历的数中取一个最大值/最小值即可
这个性质非常符合优先队列,当然multiset也可以
我用的multiset写的
代码如下:
void solve(){ int ans = 0; cin >> n >> m; vector<int> a(n + 10); for(int i = 1;i > a[i]; int res = 0; multiset<int> s; for(int i = m;i >= 2;i--) { res += a[i]; s.insert(a[i]); if(res > 0) { ans++; res -= 2 * (*prev(s.end())); s.erase(prev(s.end())); } } s.clear(); res = 0; for(int i = m + 1;i <= n;i++) { res += a[i]; s.insert(a[i]); if(res < 0) { ans++; res -= 2 * (*s.begin()); s.erase(s.begin()); } } cout << ans << endl;}