CF链接:Least Prefix Sum
Luogu链接:Least Prefix Sum
$ {\scr \color {CornflowerBlue}{\text{Solution}}} $
先来解释一下题意:
给定一个数组,问最少把多少个数变成相反数,使得$ \forall \cal{i}$,$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$
发现对于所有数据点,$ \cal{n} \le 2 \times 10^5$,说明需要 $ Ο(\cal{n \log n}) $ 或者 $ O(\cal{n}) $的算法。
分析一下题目,发现要分成$ \cal{i} > \cal{m}$ 与$ \cal{i} < \cal{m}$两种情况分类讨论
- 当 $\cal{i}$ $ > \cal{m}$时:
什么时候才能使$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$ 成立呢?
是不是只要使新加的每一段都小于等于0就行了?($ \sum_{k=m}^i a_k$ $ \le$ $ 0$)
也很好证明:一个数($ \sum_{k=1}^m a_k$)加上一个小于等于0的数($ \sum_{k={m+1}}^i a_k$),一定不大于原数。
- 当 $\cal{i}$ $ < \cal{m}$时:
同理,只要使后加的每一段都小于等于0就行了($ \sum_{k=i}^i a_k$ $ \ge$ $ 0$)
也很好证明:一个数($ \sum_{k=1}^i a_k$)加上一个大于等于0的数($ \sum_{k=i}^m a_k$),一定不小于原数。
而且,由于这两种情况类似(博主太懒),那就只考虑当 $\cal{i}$ $ > \cal{m}$的情况吧。
问题已经转化完了,接下来怎么办?
第一眼想到的是贪心。
设当前要取第$\cal{i}$个。
有一个不成熟的贪心:如果目前累加和加上$a_i$还是小于等于$0$的,就加上$a_i$,如果大于$0$了,就把$a_i$取反,$ ans+1$。
Hack数据
5 1 1 -1000 999 2 3
我们只要把999 变成-999就行了,但如果按上面贪心方法,我们要把2,3都改变!
那么贪心就不可以用了吗?
有个神奇的东西交叫反悔贪心!
简单说一下:对于当前不是最优的情况,留到后面重新选择。
我们肯定要让每次改变值后,获得综合最小的值,但当前的选择又不一定最有优。
我们可以用一个优先队列维护,到了每次要改的时候,从优先队列中选出一个收益最大(使目前累加和最大或最小)的值修改。
注意开$ \cal{long long}$并且清空优先队列!
Code(赛时代码,过丑见谅QwQ):
#include<bits/stdc++.h> #define L long long using namespace std; L a[200005]; priority_queue<L,vector<L>,greater<L> > q; int main() { int t; scanf("%d",&t); while(t--) { while(!q.empty()) q.pop(); int n,m,ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); if(n==1) { printf("0\n"); continue; } if(m==1) { L mu=0; for(int i=m+1;i<=n;i++) { if(a[i]>=0) mu+=a[i]; else if(a[i]<0 && mu+a[i]>=0) { q.push(a[i]); mu+=a[i]; } else { ans++; q.push(a[i]); mu+=a[i]; mu-=2*q.top(); q.pop(); } } printf("%d\n",ans); continue; } L mu=0; for(int i=m+1;i<=n;i++) { if(a[i]>=0) mu+=a[i]; else if(a[i]<0 && mu+a[i]>=0) { q.push(a[i]); mu+=a[i]; } else { ans++; q.push(a[i]); mu+=a[i]; mu-=2*q.top(); q.pop(); } } while(!q.empty()) q.pop(); mu=0; for(int i=m;i>=2;i--) { if(a[i]<=0) mu+=a[i]; else if(a[i]>0 && mu+a[i]<=0) { q.push(-a[i]); mu+=a[i]; } else { ans++; q.push(-a[i]); mu+=a[i]; mu+=2*q.top(); q.pop(); } } printf("%d\n",ans); } return 0; }
标签:int,题解,Sum,ans,CF,mu,cal,sum,贪心 From: https://www.cnblogs.com/201929-whx/p/17056454.html