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;}