購買裝備

發(fā)布時(shí)間: 2017年7月9日 18:17?? 最后更新: 2017年7月9日 21:05?? 時(shí)間限制: 1000ms?? 內(nèi)存限制: 128M

描述

最近盛大的一款游戲傳奇世界極其火爆。游戲玩家John，想購買游戲中的裝備。已知游戲的商店里有n件裝備，第i件裝備具有屬性值ai，購買需要花費(fèi)bi個(gè)金幣。John想去購買這些裝備，但是賬號(hào)中只有m個(gè)金幣，John是個(gè)很貪婪的家伙，他想購買盡可能多的裝備。并且在保證購買到最多件裝備的情況下，他還想讓他所購買的裝備當(dāng)中擁有最小屬性值的裝備的屬性值盡可能大。

輸入

輸入測試組數(shù)T，每組數(shù)據(jù)第一行輸入整數(shù)n(1<=n<=100000)和m(1<=m<=109), 接下來有n行，第i行有兩個(gè)數(shù)ai,?bi(1<=ai,bi<=10000).

輸出

對(duì)于每組數(shù)據(jù)，輸出兩個(gè)數(shù)字，第一個(gè)數(shù)字代表John最多可以購買的裝備數(shù)，第二個(gè)數(shù)代表在John購買最多件裝備的前提下，所購買的裝備當(dāng)中擁有最小屬性值的裝備的最大屬性值(輸入數(shù)據(jù)保證至少可以購買一件裝備)

樣例輸入1 1 2 4 3 2 2 3 樣例輸出1 1 3

題解：

注意最后加粗的一句話“最小屬性值的裝備的屬性值盡可能大”，最大化最小值問題，非常典型的二分Check問題。

這個(gè)問題，我們要輸出最多能購買的裝備的數(shù)量，然后再這個(gè)基礎(chǔ)上再最大化最小值

對(duì)于求最多能購買的裝備的數(shù)量問題，毫無疑問是一個(gè)非常簡單的貪心問題。

我們先預(yù)處理按照價(jià)值排個(gè)序，然后貪心選取價(jià)值最小的裝備，得到最多的裝備數(shù)量記為max_num

然后，我們對(duì)屬性值進(jìn)行二分Check，Check函數(shù)描述如下（原數(shù)組已按照價(jià)值作為關(guān)鍵字排序）：

對(duì)于裝備數(shù)組，從前往后掃描，對(duì)于所有滿足條件（價(jià)值小于等于剩余錢數(shù) ? 且 ? 屬性值大于等于被check值）的裝備進(jìn)行選取

判斷所選取的裝備數(shù)能否達(dá)到max_num

AC代碼：

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> pii; pii ps[100007]; int n,m; bool check(int mid,int min_num){int res = 0;int remain = m;for(int i = 0;i < n;i++){if(remain >= ps[i].first && ps[i].second >= mid){remain -= ps[i].first;res++;}}return res >= min_num; } int main(){int T;scanf("%d",&T);while(T--){int INF = 0;int max_num = 0;scanf("%d%d",&n,&m);for(int i = 0;i < n;i++){int a,b;scanf("%d%d",&a,&b);ps[i] = make_pair(b,a);INF = max(INF,b);}sort(ps,ps+n);int remain = m;for(int i = 0;i < n;i++){remain -= ps[i].first;if(remain < 0){max_num = i;break;}}if(!max_num) min_num = n;int l = 0,r = INF + 1;while(r - l > 1){int mid = (l + r) / 2;if(check(mid,min_num)) l = mid;else r = mid;}printf("%d %d\n",max_num,l);}return 0; } /* 1 2 4 3 2 2 31 4 4 2 1 2 2 2 3 2 4 */

總結(jié)

以上是生活随笔為你收集整理的2017上海金马五校 购买装备 贪心+二分Check的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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