•参考资料
[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
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define mem(a,b) memset(a,b,sizeof(a)) 5 const int maxn=1e5+50; 6 7 int n; 8 int a[maxn]; 9 struct Heap 10 { 11 int v; 12 bool op;///op == 1 : 当前这个物品作为了中转物品 13 bool operator < (const Heap &obj)const 14 { 15 if(v != obj.v) 16 return v > obj.v; 17 return op < obj.op;///中转物品优先 18 } 19 }; 20 priority_queue<Heap >q; 21 22 23 void Solve() 24 { 25 while(!q.empty()) 26 q.pop(); 27 28 ll ans=0; 29 int cnt=0; 30 for(int i=1;i <= n;++i) 31 { 32 if(!q.empty() && q.top().v < a[i]) 33 { 34 Heap tmp=q.top(); 35 q.pop(); 36 37 ans += a[i]-tmp.v; 38 if(!tmp.op)///如果tmp为非中转物品，那么在此处就有一次交易操作 39 cnt++; 40 41 q.push({a[i],true}); 42 } 43 q.push({a[i],false}); 44 } 45 printf("%lld %d ",ans,cnt<<1); 46 } 47 int main() 48 { 49 int T; 50 scanf("%d",&T); 51 while(T--) 52 { 53 scanf("%d",&n); 54 for(int i=1;i <= n;++i) 55 scanf("%d",a+i); 56 57 Solve(); 58 } 59 return 0; 60 }
