Codeforces Round #241 (Div. 2) C

題目鏈接：C. Booking System

題意：n個旅游團，每個團有一定人數，和開銷，現在一個餐館有k個桌子，每個桌子能坐一定人數，要把這些桌子分配給旅游團，一定要能坐的人數大於旅游團人數才能坐下，問最多能賺的錢，並輸出旅游團桌子匹配方案。

思路：貪心，從錢最多的旅游團開始放，每次從最小的桌子開始找，然後注意最後輸出的id號，所以排序前要多存一個id

代碼：

#include 
#include 
#include 
using namespace std;
const int N = 1005;

int n, vis[N], k;
struct Visit {
    int num, value, id;
} v[N];

struct Table {
    int num, id;
} t[N];

bool cmp(Visit a, Visit b) {
    if (a.value != b.value)
    return a.value > b.value;
    return a.num > b.num;
}

bool cmp2(Table a, Table b) {
    return a.num < b.num;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    scanf("%d%d", &v[i].num, &v[i].value);
    v[i].id = i;
    }
    sort(v, v + n, cmp);
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
    scanf("%d", &t[i].num);
    t[i].id = i;
    }
    sort(t, t + k, cmp2);
    int ans1 = 0, ans2 = 0, ans[N];
    memset(ans, -1, sizeof(ans));
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
        if (vis[j]) continue;
        if (t[j].num >= v[i].num) {
        vis[j] = 1;
        ans[i] = t[j].id;
        ans1++;
        ans2 += v[i].value;
        break;
        }
    }
    }
    printf("%d %d\n", ans1, ans2);
    for (int i = 0; i < n; i++) {
    if (ans[i] == -1) continue;
    printf("%d %d\n", v[i].id + 1, ans[i] + 1);
    }
    return 0;
}