【2018 CCPC网络赛】1001

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6438

获得最大的利润，将元素依次入栈，期中只要碰到比队顶元素大的，就吧队顶元素卖出去，答案加上他们期中的差值，并把新加入的元素用map标记为中间变量，若以后再卖出这件物品，可看做直接由之前的最小值卖出，而该中间变量重新入队，当做从未买卖过；

因为买入=买出，故输出只需将times*2即可；

也可在每个元素入队和交易最小变量时都times++，结果输出时减去队内元素数目即可；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<map>
 5 using namespace std;
 6 
 7 #define LL long long
 8 const int N = 1e5+5;
 9 int T, n;
10 priority_queue<LL, vector<LL>, greater<LL>> Q;
11 map<LL, int> vis;
12 
13 int main()
14 {
15     scanf("%d", &T);
16     while(T--)
17     {
18         vis.clear();
19         while(!Q.empty()) Q.pop();
20         scanf("%d", &n);
21         
22         LL times=0, ans=0;
23         for(int x,i=0; i<n; i++) {
24             scanf("%d", &x);
25             Q.push(x);
26             LL minx = Q.top();
27             if(x <= minx) continue;
28             
29             Q.pop();
30             ans += x-minx; times++;
31             vis[x]++;
32             if(vis[minx] > 0) {
33                 vis[minx]--;
34                 Q.push(minx);
35                 times--;
36             }
37         }
38         printf("%lld %lld
", ans, times*2);
39     }
40     return 0;
41 }