Buy and Resell
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2441 Accepted Submission(s): 924
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.
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.
4
1 2 10 9
5
9 5 9 10 5
2
2 1
5 2
0 0
In the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16
In the second case, he will buy in 2 and resell in 4. profit = - 5 + 10 = 5
In the third case, he will do nothing and earn nothing. profit = 0
#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
#include<assert.h>
#include<functional>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
const ll mod=;
ll powmod(ll a,ll b) {ll res=;a%=mod; assert(b>=); for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int T;
int n;
ll val;
int main()
{
cin>>T;
priority_queue<pll, vector<pll>, greater<pll> > que;
while(T--)
{
while(que.size()) que.pop();
cin>>n;
ll ans=;
ll num=;
for(int i=;i<n;i++)
{
cin>>val;
if(que.size()&&que.top().fi<val)
{
num++;
pll tmp=que.top(); que.pop();
ans+=val-tmp.fi;
if(tmp.se==)num--;
else num++;
que.push(mp(val,));
que.push(mp(val,));
}
else
que.push(mp(val,));
}
cout<<ans<<" "<<num<<endl;
}
return ;
}