題目

題意：

n個(gè)寶石，寶石的買入或賣出價(jià)格固定，一天只能到一個(gè)珠寶商店（從左到右），問最大利潤(rùn)是多少？在保證最大利潤(rùn)的同時(shí)最少交換次數(shù)是多少？

題解：

題目有兩問：一個(gè)是求利潤(rùn)，一個(gè)是求次數(shù)
利潤(rùn)就是低價(jià)買高價(jià)賣就行
比如1 2 10，1的時(shí)候買，2的時(shí)候賣，2的時(shí)候買，10的時(shí)候賣，這樣一共掙了1+8=9，但是如果我們1的時(shí)候買，10的時(shí)候賣也是掙9，而且次數(shù)還少一次
我們?cè)撊绾斡涗涀钌俅螖?shù)?
利用優(yōu)先隊(duì)列
首先我們計(jì)算最大利潤(rùn)時(shí)就用第一個(gè)步驟，即1買2賣，2買10賣，當(dāng)我們賣完一個(gè)寶石時(shí)就標(biāo)記一下，若次元素再次出現(xiàn)在隊(duì)首，就說明出現(xiàn)了1 2 10的情況。。然后pop原本，加入當(dāng)前的（即彈出2，加入10），這樣始終可以保持最佳
最后根據(jù)剩余標(biāo)記情況計(jì)算交換次數(shù)
也就是每個(gè)寶石分為兩個(gè)
其實(shí)我們要找的就是遞增關(guān)系

代碼：

#include<bits/stdc++.h> #define ll long long #define PII pair<int,int> using namespace std; const int N = 1e6+5; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; struct node{ll num,index;node(ll a,ll b){num = a;index = b;}friend bool operator < (node a,node b){if(a.num == b.num) return a.index < b.index; //從低到高（未標(biāo)記的在前面） return a.num > b.num;//價(jià)格從高到低 } }; priority_queue <node> q; int main() {ll t,p,i,j,k,n,x;cin>>t;while(t--){cin>>n;ll ans = 0,count = 0;for(i = 1;i <= n;i++){cin>>x;q.push(node(x,0)); node temp = q.top();if(x > temp.num)//如果賣出價(jià)錢比已買的最高價(jià)錢還高 {ans += x-temp.num;//賣出 q.pop();q.push(node(x,1));//標(biāo)記后加入}}while(!q.empty()){if(q.top().index) count++;q.pop();}printf("%lld %lld\n",ans,count*2);} }

總結(jié)

以上是生活随笔為你收集整理的Buy and Resell 2018中国大学生程序设计竞赛 - 网络选拔赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。