多少年不写题了... (我把每一天看作是一个商品,第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; }转载于:https://www.cnblogs.com/liu-runda/p/9877407.html
相关资源：数据结构—成绩单生成器