•参考资料
[1]:HDU6438（优先队列+思维）
•题意
有n个城市，第 i 天你会达到第 i 个城市；
在第 i 个城市中，你可以用 ai 元购买一个物品，或者用 ai 元卖掉一个物品，你可以同时保存多个物品。
最开始你身上没有物品，但是有无限的金钱；
让你求从城市 1 走到城市 n，最大的收益以及最少的交易次数。
•题解
假设你当前在第 i 个城市，这个城市的物价为 $a_i$ 元；
但是你要不要购买这个物品呢？
因为我们不确定第 i+1~n 个城市是否有物价高于 $a_i$ 的城市；
所以，我们可以选择先将 $\{i,a_i \}$ 加入购物车；
如果这之后存在更高物价的城市，就将 $\{i,a_i \}$ 下单，然后转手就卖；
假设第 j 个城市的物价 $a_j > a_i$；
那么，我们将 $\{i,a_i \}$ 下单，并以 $a_j$ 的价格出售，获得 $a_j-a_i$ 元的利润；
此时，第 $i,j$ 城市已经进行了一次操作，按理说不能在做其他操作了；
但是，如果你来到的下一个 k 城市的物价 $a_k > a_j > a_i$ 呢？
是不是将 $a_i$ 在此处卖更划算？
我们考虑一下，虽然 j 城市做了 卖 这个操作，但是我们还是可以将其加入到购物车中的；
因为，如果遇到比 $a_j$ 更大的物价，我们可以反悔一下，在第 j 个城市不出售 $a_i$；
而是在物价更高的 k 城市出售 $a_i$，这种决策才能获得更高的利润 $a_k-a_i$；
但是，你会发现 $a_k-a_i = (a_j-a_i)+(a_k-a_j)$，也就是说，就算是 $a_i$ 在 j 城市出售，也可以将 $\{ j,a_j \}$ 加入到购物车中；
只不过，在第 k 个城市出售 $a_j$ 并不是真的将 $a_j$ 卖出，而是将 $a_i$ 卖出；
但是，将 $a_i$ 卖出后，$a_j$ 依旧应该存在于购物车中，所以，我们要将 $\{ j,a_j\}$ 加入购物车两次；
并且，我们希望购物车按照从小到大的顺序排列，因为这样的话，遇到新城市，我们可以优先下单物件低的以此来获得更大的利润；
考虑到物品按照价格升序排列，我们可以用优先级队列；
•Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+; int n;
int a[maxn];
struct Heap
{
int v;
bool op;///op == 1 : 当前这个物品作为了中转物品
bool operator < (const Heap &obj)const
{
if(v != obj.v)
return v > obj.v;
return op < obj.op;///中转物品优先
}
};
priority_queue<Heap >q; void Solve()
{
while(!q.empty())
q.pop(); ll ans=;
int cnt=;
for(int i=;i <= n;++i)
{
if(!q.empty() && q.top().v < a[i])
{
Heap tmp=q.top();
q.pop(); ans += a[i]-tmp.v;
if(!tmp.op)///如果tmp为非中转物品，那么在此处就有一次交易操作
cnt++; q.push({a[i],true});
}
q.push({a[i],false});
}
printf("%lld %d\n",ans,cnt<<);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d",a+i); Solve();
}
return ;
}