2017金马五校赛 K.购买装备（二分）

思路：题目要求在最多装备的基础上属性值最小值要最大，典型的求最大化最小值问题。这里求最多装备数量是简单的，接着就是二分答案求最大化最小属性值。

在这mark了一下，可以去看看这篇文章关于提高cin/cout的效率

下面是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;

struct point{
    int a,b;
}num[100005];

int n,m,sum,k;
int l,r,mid,t,ans;

int cmp(point a,point b)
{
    return a.b<b.b;
}

int main()
{
    //ios::sync_with_stdio(false);    //试了一下新学到的操作，能提高cin/cout的效率
    //cin.tie(0);                     //
    int T;
    //cin>>T;
    scanf("%d",&T);
    while(T--)
    {
        //cin>>n>>m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            //cin>>num[i].a>>num[i].b;
            scanf("%d%d",&num[i].a,&num[i].b);
        sort(num,num+n,cmp);
        sum=0;
        k=0;
        for(int i=0;i<n;i++)
        {
            sum+=num[i].b;
            if(sum>m)
            {
                break;
            }
            k++;
        }
        l=0,r=10000,ans=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            sum=0;
            t=0;
            for(int i=0;i<n;i++)
            {
                if(num[i].a>=mid)
                {
                    sum+=num[i].b;
                    if(sum<=m) t++;
                }
            }
            if(t<k)
                r=mid-1;
            else
                ans=mid,l=mid+1;
        }
        //cout<<k<<' '<<ans<<endl;
        printf("%d %d\n",k,ans);
    }
}