HDU 6438 Buy and Resell (CCPC网络赛) 堆贪心-白红宇

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

阅读量：6086 次

发布时间：2019-06-20

本文共 4119 字，大约阅读时间需要 13 分钟。

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

1. spend

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
        
         #define N 100009using 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
         
           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\n",ans,time*2);   //一次交易涉及兩個城市，時間是交易次數的兩倍    }}

转载于:https://www.cnblogs.com/Lin88/p/9537354.html

你可能感兴趣的文章

C#~异步编程再续~你必须要知道的ThreadPool里的throw