[hdoj6438]Buy and Resell

[hdoj6438]Buy and Resell

题意

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

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

问最多能赚多少钱?

题解

贪心 + 数据结构

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

  • $1$表示他是之前买入并且在这次卖出
  • $2$表示他是没有买卖,直接抵消了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}