多少年不写题了...
(我把每一天看作是一个商品,第i天是第i个商品)
一开始看了半天看出来一个性质:买的所有商品中最贵的不会比卖的所有商品中最便宜的贵,然后似乎没有什么用处....
所以最后还是看题解了.
关键在于,从前x天的最优策略必然可以通过至多一次修改得到前(x+1)天的最优策略.
(所谓前x天的最优策略就是假设只有前x天,x天之后不再操作时的最优策略)
首先,第(x+1)天如果不进行操作,最优策略必然和前x天的时候一样.
如果进行操作,必然只能在第(x+1)天卖出,那就必须保证在第(x+1)天的时候手里剩下一个商品.
也就是说,我们现在要求一个方案,使得第x天结束的时候手里恰好有1个商品,在这个前提下赚到最多的钱(付出的钱最少).
由我们的前提,我们现在已经知道一个最优方案,可以在第x天结束的时候手里有0个商品了.假设这个最优方案买了y次卖了y次.那么我们要的x天后剩下一个商品的最优方案必然可以通过买y次卖y次的最优方案基础上少卖一次/多买一次之后得到(也就是说,考虑卖掉的商品中最便宜的z,以及前x个当中没买的商品中最便宜的w,不卖z或者买下w).
我们把买y个卖y个的最优方案记作S(y,y).修改一次之后得到的最优方案其实是这么得到的:按照价格从低到高考虑每一个商品,找到第一个没有被购买的商品Q(可能是出售,也可能是不操作),买下来.(其实是"不操作变成购买","出售变成不操作").比这个商品价格更低的商品一定都被购买了
那么接下来考虑S(y+1,y)/S(y,y-1)中的最优方案S2,假设不是S(y,y)修改一次之后得到的,看看会发生什么.
这个所谓的S2中,如果对Q执行的操作是购买或不操作,而且"少买一个Q/多卖一个Q"之后还是合法方案,那就把购买Q变成不操作,不操作变成出售Q,就能得到一个比S(y,y)还要好的方案.
证不出来了....先坑着...太菜了...
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
int main(){
int T;scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int x;
priority_queue<int,vector<int>,greater<int> > bought,sold,tobuy;
int cnt=0;
ll ans=0;
for(int i=1;i<=n;++i){
scanf("%d",&x);
bool flag1=!tobuy.empty()&&x>tobuy.top();
bool flag2=!sold.empty()&&x>sold.top();
if(flag1&&(!flag2)){
int y=tobuy.top();tobuy.pop();
ans+=x-y;bought.push(y);sold.push(x);
cnt++;
}else if((!flag1)&&flag2){
int y=sold.top();sold.pop();
sold.push(x);tobuy.push(y);
ans+=x-y;
}else if(flag1&&flag2){
int dlt1=x-tobuy.top(),dlt2=x-sold.top();
if(dlt2>=dlt1){
int y=sold.top();sold.pop();
sold.push(x);tobuy.push(y);
ans+=x-y;
}else{
int y=tobuy.top();tobuy.pop();
ans+=x-y;bought.push(y);sold.push(x);
cnt++;
}
}
else tobuy.push(x);
}
printf("%lld %d\n",ans,cnt*2);
}
return 0;
}