HDU 6438 Buy and Resell (CCPC网络赛) 堆贪心

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

The Power Cube is used as a stash of Exotic Power. There are

Input

There are multiple test cases. The first line of input contains a positive integer

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

1 2 10 9

9 5 9 10 5

2 1

Sample Output

16 4

5 2

0 0

Hint

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

本題大意：

　　商人從左往右走不回頭，進行買賣交易，每個城市的貨物價格不同，要求商人的賺取的最大利潤，以及獲得次最大利潤的最少時間（涉及的城市個數）

解題思路：

　　這題是筆者首次參加CCPC網絡賽時遇到的題目，當時想不出來，水平很有限。回來之後聽取各方大佬的講解后把題補掉了。本題的做法是，用堆來實現貪心，每到一個城市，看前面的城市中的有沒有價格更低的地方，如果有，那麼就把這兩個城市作為一對交易。這樣怎麼實現利益最大化呢？接下來的操作就是關鍵，賣出的城市留在隊列中，這樣賣出的城市還可以作為買入的地方，如果一個城市一開始作為了賣出的城市，後來還作為了買入的城市，那就相當於在那個城市不買不賣，把兩對交易合成一對，中間的城市相當於沒參與交易。

　　下面看我手跑一邊樣例就清楚了：

　　1、首先是第一個入隊，第二個入隊時開始判斷，第二個是2，堆頂1，可以構成交易，進行交易，把1彈出隊。買的要彈出隊列，但賣的不用，因為賣的地方可以再買，而買的地方不會再賣，因為如果後面要發生反悔，中間著永遠是賣的地方（看下面的2、就明白了），2只需要打上一個賣出標誌、交易次數+1，然後進隊。

　　2、10入隊，可以和堆頂的2構成買賣，但2有賣出標誌，這個時候，從1買入從2賣出，再從2買入從10賣出，相當於從1買入從10買出，2成了中間量。為了減少次數，我們直接讓1和10構成交易，2的賣出標誌去掉（不需要出隊）、交易次數不變，還是1次。

　　3、9入隊，可以和堆頂的2構成交易，2沒有賣出標誌了，就是一個普通買入地，把2彈出隊列。交易次數+1

　　這樣這組數據就跑完了。發生兩次交易，交易金額是-1-2+10+9=16，發生的交易次數是2，時間是兩倍：4

這裡用了優先隊列來維護一個最小堆

下面是AC代碼

#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;

struct node
{
    int x,v;        //x是坐標，v是這個城市的價格
    bool sell;
    friend bool operator <(node a,node b)
    {
        if(a.v==b.v)
            return !a.sell;     //同價格中：曾經在那個城市買過的優先

        return a.v > b.v;   //優先隊列中價格小的優先
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        priority_queue<node> q;
        int n;
        scanf("%d",&n);

        int a;
        scanf("%d",&a);     //第一個入隊
            node temp;
            temp.x=1;
            temp.v=a;
            temp.sell=false;
            q.push(temp);

        ll ans=0,time=0;
        for(int i=2;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            temp.sell=false;
            if(a>q.top().v)        //如果在這之前有價格比它低，則賣出
            {
                node top=q.top();
                q.pop();
                ans+=a-top.v;
                if(top.sell)        //如果曾經在那個城市賣出過，又再那個城市買入
                {
                    top.sell=false; //那就相當于沒有交易過，兩次交易合為一次，故次數不加
                    q.push(top);
                }
                else
                    time++;         //反之次數增加

                temp.sell=true;
            }
            temp.x=i;               //當前城市入隊
            temp.v=a;
            q.push(temp);
        }
        printf("%lld %lld
",ans,time*2);   //一次交易涉及兩個城市，時間是交易次數的兩倍

    }
}