题目链接：http://acmoj.shu.edu.cn/problem/420/ 题意： 最近盛大的一款游戏传奇世界极其火爆。游戏玩家John，想购买游戏中的装备。已知游戏的商店里有n件装备，第i件装备具有属性值ai，购买需要花费bi个金币。John想去购买这些装备，但是账号中只有m个金币，John是个很贪婪的家伙，他想购买尽可能多的装备。并且在保证购买到最多件装备的情况下，他还想让他所购买的装备当中拥有最小属性值的装备的属性值尽可能大。 规模： n:[1,1e5] m:[1,1e9] a,b:[1,1e4] 类型： 贪心+二分 分析：
一眼望过去像是个背包，可是数据太大了。那么分析一下复杂度，应该是个nlogn的算法。当时只想到了排序+贪心，贪心没考虑好，发现只能过样例。 正解： 根据题目，贪心的拿最多件，就是说按照价格排序拿前面的，所以装备数maxnum是固定的。 接着我们二分最小属性minpro，然后挑选属性比minpro大的，根据价格排序的前maxnum件，判断总花费是否比m个金币大。 这里我们都是按金币比较的，所以只需要一次排序。
时间复杂度&&优化： nlogn 代码：
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <queue> #include<stack> #include<math.h> #include<vector> #include<algorithm> #include<iostream> using namespace std; const int MAXN = 100005; const int MAXM = 5005; const int inf = 1000000007; const int mod = 1000000007; int n,m; int T,maxnum; struct node{ int pro; int cost; }; node q[MAXN]; bool cmp(node a,node b){ if(a.cost==b.cost){return a.pro<b.pro;} else return a.cost<b.cost; } bool judge(int minpro){ int sum=0,num=0; for(int i=0;i<n;i++){ if(q[i].pro>=minpro){ sum+=q[i].cost; num++; } if(num==maxnum){ if(sum<m)return true; else return false; } } if(num<maxnum){ return false; } } int main() { scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d%d",&q[i].pro,&q[i].cost); } sort(q,q+n,cmp); // for(int i=0;i<n;i++){ // cout<<q[i].pro<<" "<<q[i].cost; // } int sum=0; maxnum=0; for(int i=0;i<n;i++){ if(sum+q[i].cost<m){ sum+=q[i].cost; maxnum++; } else break; } int l=0,r=10005; int mid=(l+r)/2; while(r-l>1){ //cout<<l<<" "<<r<<endl; mid=l+(r-l)/2; if(judge(mid)){ l=mid; } else{ r=mid; } } cout<<maxnum<<" "<<l<<endl; } return 0; }