HDU6438---Buy and Resell

HDU6438---Buy and Resell

定义a[i]：i城市的能量块价格

考虑这样一种情况：有四个城市的能量块价格为a1，a2，a3，a4

①如果a3，a4均大于a1，a2，那么利润为(a3+a4)-(a1+a2)

②如果a2<a4<a1<a3，如果a3与a2结合那么a4无法与a1结合此时利润x为(a3-a2)；如果a3与a1结合，那么利润y为(a4-a2)+(a3-a1)；x=a3-a2=(a3-a1)+(a1-a2)，y=(a4-a2)+(a3-a1)，明显有x>y，且产生x需要的交易次数更少

由上可知，如果当前处于i，对于所有a[i]>a[j]（j<i），取最小的a[j]与之结合产生的利润最大，因而可用优先队列；但是以当前价格卖出可能并非最好的选择，考虑这样一种情况：

a2<a1<a3<a4<a5，如果现在以a3的价格卖掉a2，以a4的价格卖掉a1，到了城市5，以a5的价格价格卖掉a1更加划算；

因而每次能够产生利润时要把当前的出售价格压入队列，这样可以留住以后以更高的价格出售的可能性；如果之后到了城市k，a[k]>a[i]，且a[i]的价格已经是能够结合的价格中的最小值，可以直接让a[k]与a[j]结合而非a[i]，交易次数进一步减少

#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define Fov(i,x,y) for(int i=(x);i>=(y);--i)
#define Fo(i,x,y) for(int i=(x);i<(y);++i)
#define midf(a,b) ((a)+(b)>>1)
#define L(_) (_)<<1
#define R(_) ((_)<<1)|1
#define fi first
#define se second
#define ss(_) scanf("%s",_)
#define si(_) scanf("%d",&_)
#define sii(x,y) scanf("%d%d",&x,&y)
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sl(_) scanf("%lld",&_)
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
inline int read()
{
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
    while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int n_max=1e5+10;
int a[n_max];

int main()
{
	//freopen("in.txt","r",stdin);
	int T; si(T);
	while(T--)
    {
        int n,cnt=0,x; si(n);
        For(i,1,n) si(a[i]);
        priority_queue<int,vector<int>,greater<int> >q;
        map<int,int>m;
        ll ans=0;
        For(i,1,n)
        {
            if(!q.empty()&&a[i]>(x=q.top()))
            {
                ans+=a[i]-x; q.pop();
                ++cnt; ++m[a[i]]; q.push(a[i]);
                if(m[x])
                {
                    --m[x];
                    --cnt;
                }
            }
            q.push(a[i]);
        }
        printf("%lld %d\n",ans,cnt<<1);
    }
	return 0;
}