题意

有n个城市，你会从前往后依次到达每个城市，你每次可以用a[i]元购买或者卖掉一个物品，你可以同时保存无限个个物品。最开始你身上没有物品，但是有无限的金钱，现在问你最大的收益是多少。

思路

用优先队列维护到当前位置的最优值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long LL;
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        int n; scanf("%d", &n);
        priority_queue<int, vector<int>, greater<int> > pq;
        map<int, int> mp;
        LL res = 0, cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int x; scanf("%d", &x);
            if (!pq.empty() && pq.top() < x)
            {
                int u = pq.top(); pq.pop();
                res += x-u;
                pq.push(x);
                cnt++;
                if (mp[u]) mp[u]--, cnt--;
                mp[x]++;
            }
            pq.push(x);
        }
        printf("%lld %lld\n", res, cnt*2);
    }
    return 0;
}
/*
3
4
1 2 10 9
5
9 5 9 10 5
2
2 1
*/