题意:
给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 <= n;i++) cin >> 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;
}