转载请注明出处:http://tokitsukaze.live/

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6438


题意:
在一个数轴上有n个点,为1到n。每个点上有个值v。你可以在一个点上选择:买入一个商品花费v,卖出一个商品赚取v(如果手持有商品的话),什么都不干。问从1走到n最多赚多少,在保证赚取最多的情况下,输出最少的交易次数。


题解:
用优先队列维护一个结构体{v,cnt}。v表示某个点的价值,cnt表示那个点是不是卖出点。优先队列先出v小的,v相同先出cnt=1的。因为要求交易次数最少,价格相同时,把卖出点作为中转点,先出队,就能满足这个要求。
每次走到一个点,如果点的价值v比优先队列中最小值大,就更新答案,然后推入{v,1}。然后每个点固定推入{v,0}。最后统计优先队列中cnt=1的个数*2就是最少交易次数。

比如:1 2 5。
第1个点:入{1,0}
第2个点:出{1,0},ans+=2-1=1,入{2,1},入{2,0}。
第3个点:出{2,1},ans+=5-2=4,入{5,1},入{5,0}。
最后优先队列中有:{2,0},{5,1},{5,0}。
最少交易次数为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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=1e9+7;
/********************************* head *********************************/
struct node
{
ll v,cnt;
node(){}
node(ll _v,ll _cnt):v(_v),cnt(_cnt){}
friend bool operator <(node a,node b)
{
if(a.v==b.v) return a.cnt<b.cnt;
return a.v>b.v;
}
};
ll a[MAX];
void go()
{
int t,n,i;
ll ans,cnt;
node tmp;
read(t);
while(t--)
{
read(n);
for(i=0;i<n;i++) read(a[i]);
ans=0;
priority_queue<node> q;
for(i=0;i<n;i++)
{
if(sz(q))
{
tmp=q.top();
if(tmp.v<a[i])
{
q.pop();
ans+=a[i]-tmp.v;
q.push(node(a[i],1));
}
}
q.push(node(a[i],0));
}
cnt=0;
while(!q.empty())
{
cnt+=(q.top()).cnt;
q.pop();
}
printf("%lld %lld\n",ans,cnt*2);
}
}