2018 CCPC 网络赛 Buy and Resell

The Power Cube is used as a stash of Exotic Power. There are 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.

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+10;
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,1,n)
    {
        scanf("%d",a+i);
    }
}
priority_queue<Item > q;

void work()
{
    Item ini(1,a[1],0);
    q.push(ini);
    int time=0;
    long long ans=0;
    rep(i,2,n)
    {
        Item now=Item(i,a[i],0);
        Item u=q.top();
      //  printf("i:%d u.w:%d u.t:%d
",i,u.w,u.t);
        if(u.w<now.w)
        {
            if(u.sell==1)
            {
                ans+=now.w-u.w;
                u.sell=0;
                q.pop();
                q.push(u);
                now.sell=1;
                q.push(now);
            }
            else
            {
                //printf("i:%d u.t:%d
",i,u.t);
                ans+=now.w-u.w;
                q.pop();
                now.sell=1;
                time+=1;
                q.push(now);
            }
        }
        else
        {
            q.push(now);
        }
    }
    printf("%lld %d
",ans,time*2);
}
void init()
{
    while(!q.empty()) q.pop();
}
int main()
{
    int T;
    scanf("%d",&T);
    rep(tt,1,T)
    {
        init();
        Input();
        work();
    }
    return 0;
}

2018 CCPC 网络赛 Buy and Resell

相关推荐