ACM模版

描述

题解

比较基础的二分+贪心，如果这里要保证的不是最多件装备而是装备价值（不是属性）最大的话，就是二分+背包，因为这里实际上默认的是装备的价值为单位一罢了，大大降低了难度。比较水~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

struct equ
{
    int a, b;
} e[MAXN], e_[MAXN];

int tmp,n,m;
int mx;

bool cmp(const equ &x, const equ &y)
{
    return x.b < y.b;
}

bool cmp_(const equ &x, const equ &y)
{
    return x.a < y.a;
}

int check(int x)
{
    int m = tmp;
    int res = 0;
    for (int i = 0; i < n && m >= e[i].b && res < mx; i++)
    {
        if (e[i].a >= x)
        {
            res++;
            m -= e[i].b;
        }
    }
    if (res == mx)
    {
        return 1;
    }

    return 0;
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

template <class T>
inline void print_d(T x)
{
    if (x > 9)
    {
        print_d(x / 10);
    }
    putchar(x % 10 + '0');
}

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(n), scan_d(m);
        tmp = m;
        for (int i = 0; i < n; i++)
        {
            scan_d(e[i].a), scan_d(e[i].b);
            e_[i] = e[i];
        }
        sort(e, e + n, cmp);
        sort(e_, e_ + n, cmp_);

        mx = 0;
        for (int i = 0; i < n && m >= e[i].b; i++)
        {
            mx++;
            m -= e[i].b;
        }
        printf("%d ", mx);

        int l = 0, r = n - 1, m;
        int res = e_[0].a;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if (check(e_[m].a))
            {
                res = e_[m].a;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }

        printf("%d\n",res);
    }

    return 0;
}