2018中国大学生程序设计竞赛 - 网络选拔赛 1001 Buy and Resell

Buy and Resell

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

The Power Cube is used as a stash of Exotic Power. There are n cities numbered 1,2,…,n where allowed to trade it. The trading price of the Power Cube in the i-th city is ai dollars per cube. Noswal is a foxy businessman and wants to quietly make a fortune by buying and reselling Power Cubes. To avoid being discovered by the police, Noswal will go to the i-th city and choose exactly one of the following three options on the i-th day:
\1. spend ai dollars to buy a Power Cube
\2. resell a Power Cube and get ai dollars if he has at least one Power Cube
\3. do nothing
Obviously, Noswal can own more than one Power Cubes at the same time. After going to the n cities, he will go back home and stay away from the cops. He wants to know the maximum profit he can earn. In the meanwhile, to lower the risks, he wants to minimize the times of trading (include buy and sell) to get the maximum profit. Noswal is a foxy and successful businessman so you can assume that he has infinity money at the beginning.

Input

There are multiple test cases. The first line of input contains a positive integer T (T≤250), indicating the number of test cases. For each test case:
The first line has an integer n. (1≤n≤105)
The second line has n integers a1,a2,…,an where ai means the trading price (buy or sell) of the Power Cube in the i-th city. (1≤ai≤109)
It is guaranteed that the sum of all n is no more than 5×105.

Output

For each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.

Sample Input

3 4 1 2 10 9 5 9 5 9 10 5 2 2 1

Sample Output

Hint

profit = - 1 - 2 + 10 + 9 = 16

profit = - 5 + 10 = 5

profit = 0

题解:

n天,每天商品有个价格,或买或卖或不买不卖。

贪心策略:分为两个堆(或优先队列),一个堆v为储存买的价格,一个堆s储存卖的价格。第i天的商品和之前买与卖两个堆中的最小值进行比较。共分为四种情况:1.如果第i天的价格比买的堆v里最小值大,且买的堆v里最小值比卖的堆s里最小值小,则买掉买的堆v里最小的,再卖出去,交易次数加2,即v.pop(),s.push(),cnt+2。2.如果第i天的价格比卖的堆s里最小值大,且买的堆v里最小值比卖的堆s里最小值大,则买掉卖的堆s里最小的,再卖出去,意思为现在卖比之前卖的那次更划算,我们把它买回来就等于之前那次没有卖,再卖出去等于现在才卖,即s.pop(),v.push(),s.push()。3.如果当天的价格即小于s中最小又小于v中最小,则把他放到买的堆v里,即v.push()。

这样下来,最后买的堆里剩下的就是没买没卖的。

代码:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll t;
scanf("%lld",&t);
while(t--){
ll n, tmp, cnt = 0,sum = 0;
scanf("%lld",&n);
priority_queue<ll,vector<ll>,greater<ll> >v,s;
for(ll i = 0;i<n;i++){
scanf("%lld",&tmp);
if(!v.empty()){
if(!s.empty()&&tmp>s.top()&&s.top()<=v.top()){
sum+=tmp-(s.top());
v.push(s.top());
s.pop();
s.push(tmp);
}
else if(tmp>v.top()&&(s.empty()||s.top()>v.top())){
s.push(tmp);
sum+=tmp-(v.top());
v.pop();
cnt++;
}
else if(tmp<=v.top()){
v.push(tmp);
}
}
else{
if(!s.empty()&&tmp>s.top()){
v.push(s.top());
sum+=tmp-s.top();
s.pop();
s.push(tmp);
}
else
v.push(tmp);
}
}
printf("%lld %lld\n",sum,2*cnt);
}
return 0;
}

文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!