Buy and Resell hdu-6438

题意：给出n，和a[i]代表第i天东西的行价，问收益最大是多少，在此前提下交易次数最少是多少？
思路：
维护一个小根堆，每次将堆顶与a[i]比较，如果a[i]<min,直接把a[i]放入，如果a[i]>min,那么可以a[i]-min就暂且作为我当前的收益，当然这不一定是最优的方案，
考虑后面如果有a[j]>a[i]，那我这个物品肯定在a[j]卖是最划算的。如果我在a[i]卖了后，再pusha[i]进小根堆，如果到了a[j]再卖的话这个过程中，你会发现ans先加了一个a[i]-min,又加了一个a[j]-a[i]，那么其实对ans的贡献只有a[j]-min,就相当于min在a[j]这个点卖出。然后我们再考虑一下这样做是否对交易次数有影响，会发现如果这样交易次数会多加2，因此我们对中间商都需要标记一下。

#include<bits/stdc++.h>

using namespace std;
#define int long long

const int maxn = 5e5+10;

int n, a[maxn], ans = 0, cnt = 0;
priority_queue<int, vector<int>, greater<int> > q;
map<int, int> mp;

signed main()
{
    int t;
    cin >> t;
    while(t--)
    {
        while(!q.empty()) q.pop(); mp.clear();
        ans = 0, cnt = 0;
        cin >> n;
        for(int i = 0;  i< n; i++) cin >> a[i];
        q.push(a[0]);
        for(int i = 1; i < n; i++){
            int x = q.top();
            if(x < a[i])
            {
                ans += a[i]-x;
                cnt += 2;
                q.pop();

                if(mp[x])
                {
                    mp[x]--;cnt-=2;
                }
                q.push(a[i]);
                mp[a[i]]++;
            }
            q.push(a[i]);
        }
        cout << ans << " " <<cnt <<endl;
    }
}