[hdoj6438]Buy and Resell

题意

给定$n$个城市和无限制的初始金钱你可以在每个城市里

• 以$a_i$的价格买个商品
• 以$a_i$的价格卖出商品
• 啥都不做

问最多能赚多少钱？

题解

贪心 + 数据结构

假设每个城市都卖出商品。那么之前买入的最便宜的商品来卖。对于买卖次数就将假设买入的商品记录为两种

• $1$表示他是之前买入并且在这次卖出
• $2$表示他是没有买卖，直接抵消了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T,n;
ll ans = 0;
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        priority_queue<pII>pq; ans = 0;int cnt = 0;
        scanf("%d",&n);
        rep(i,0,n){
            int x;scanf("%d",&x);
            pq.push(make_pair(-x,1));
            pq.push(make_pair(-x,2));
            ll temp = x + pq.top().fi;
            if(pq.top().se == 1)  cnt+=2;
            ans += temp;
            pq.pop();
        }
        printf("%lld %d\n",ans,cnt);
    }
    return 0;
}