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.
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.
For each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.
大致题意：
一条直线路径上有n个城市，每个城市对于货物Power Cube有不同的价格，商人Ａ从起点走到终点，在每一个城市可以买一件货物，或卖一件货物，或什么都不做。商人可以携带很多件货物。初始金钱充足的情况下，问到终点的最大利润与最大利润条件下的最小交易次数。
思路：堆＋贪心。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=1e5+;
int a[MAXN];
int n;
struct Item
{
int t,w;
int sell;
Item() {}
Item(int _t,int _w,int _sell)
{
t=_t;
w=_w;
sell=_sell;
}
};
bool operator < (Item a,Item b)
{
if(a.w==b.w) return a.sell<b.sell;
else return a.w > b.w;
}
void Input()
{
scanf("%d",&n);
rep(i,,n)
{
scanf("%d",a+i);
}
}
priority_queue<Item > q; void work()
{
Item ini(,a[],);
q.push(ini);
int time=;
long long ans=;
rep(i,,n)
{
Item now=Item(i,a[i],);
Item u=q.top();
// printf("i:%d u.w:%d u.t:%d\n",i,u.w,u.t);
if(u.w<now.w)
{
if(u.sell==)
{
ans+=now.w-u.w;
u.sell=;
q.pop();
q.push(u);
now.sell=;
q.push(now);
}
else
{
//printf("i:%d u.t:%d\n",i,u.t);
ans+=now.w-u.w;
q.pop();
now.sell=;
time+=;
q.push(now);
}
}
else
{
q.push(now);
}
}
printf("%lld %d\n",ans,time*);
}
void init()
{
while(!q.empty()) q.pop();
}
int main()
{
int T;
scanf("%d",&T);
rep(tt,,T)
{
init();
Input();
work();
}
return ;
}