题目地址：Codeforces：Problem – 3B – Codeforces、洛谷：CF3B Lorry – 洛谷 | 计算机科学教育新生态

题目描述

A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It’s known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.

题意简述

有一辆能够装载容量为$v$的货车，共有$n$个货物待装。货物分为两种类型，类型1所占容量为1，类型2所占容量为2，同种类型的货物的价值可能不同。求货车最多可以装载货物的最大价值之和。

输入输出格式

输入格式：
The first line contains a pair of integer numbers n and v (1 ≤ n ≤ 10^5; 1 ≤ v ≤ 10^9), where n is the number of waterborne vehicles in the boat depot, and v is the truck body volume of the lorry in cubic metres. The following n lines contain the information about the waterborne vehicles, that is a pair of numbers ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 10^4), where ti is the vehicle type (1 – a kayak, 2 – a catamaran), and pi is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

输出格式：
In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

输入输出样例

输入样例#1：

3 2
1 2
2 7
1 3

输出样例#1：

7
2

题解

首先看到这个题就有一种强烈的直觉，即按单位容量的价值（即所谓的“性价比”）排序，先从大到小贪心地装，此时会遇到三种情况：货物的总占用容量小于货车容量，或者货车容量刚好用完，或者还剩1没有用。
对于第一种情况，直接全装进去就完事了。
对于第二种情况，直接按贪心的方案输出即可，因为根据贪心的思路，用单位价值较低的货物替换只会让方案变得更劣。
对于第三种情况，有两种选择：用未装进去的占容量为1的货物填这个空，或者把前面的某个占容量为1的货物替换为一个占容量为2的货物。第一个选择中，填空的货物肯定是未装之中价值最大的那个，而第二个选择中，肯定是用价值最大的2货物替换价值最小的1货物，这些都可以贪心地做。判断一下哪种选择更优即可。
思路比较好想，不过细节比较多，代码稍微有点难度。

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 100005;

int n, v;

struct Node {
    int no, t, p;
    bool operator>(const Node &rhs) const {
        return double(p) / t > double(rhs.p) / rhs.t;
    }
} a[MAXN];

int main() {
    n = readint(); v = readint();
    for(int i = 1; i <= n; i++) {
        a[i].t = readint();
        a[i].p = readint();
        a[i].no = i;
    }
    std::sort(a + 1, a + n + 1, std::greater<Node>());
    int mn1 = 1e9, mn1n = 0, sum = 0, i;
    for(i = 1; i <= n; i++) {
        if(v < a[i].t) break;
        if(a[i].t == 1 && a[i].p < mn1) {
            mn1 = a[i].p; mn1n = i;
        }
        v -= a[i].t;
        sum += a[i].p;
    }
    int mx1 = 0, mx1n = 0, mx2 = 0, mx2n = 0;
    for(int j = i; j <= n; j++) {
        if(a[j].t == 1 && a[j].p > mx1) {
            mx1 = a[j].p; mx1n = j;
        }
        if(a[j].t == 2 && a[j].p > mx2) {
            mx2 = a[j].p; mx2n = j;
        }
    }
    if(v == 0 || (i == n && v >= a[n].t)) {
        printf("%d\n", sum);
        for(int j = 1; j < i; j++) printf("%d ", a[j].no);
    } else {
        int ans1 = 0, ans2 = 0;
        if(mx1 != 0) ans1 = sum + mx1;
        if(mx2 != 0) ans2 = sum - mn1 + mx2;
        int ans = std::max(ans1, ans2);
        ans = std::max(ans, sum);
        printf("%d\n", ans);
        for(int j = 1; j < i; j++) {
            if(ans != sum && ans != ans1 && ans == ans2 && j == mn1n) continue;
            printf("%d ", a[j].no);
        }
        if(ans != sum && ans == ans1) printf("%d ", a[mx1n].no);
        if(ans != sum && ans != ans1 && ans == ans2) printf("%d ", a[mx2n].no);
    }
    return 0;
}