Codeforces 416C Booking System(貪心)

題目連結：Codeforces 416C Booking System

題目大意：餐館有n批客人，每批客人給出人數和消費金額。然後餐館有m個桌子，給出每個桌子可以坐的人數。問說在這一時刻，餐館可以最大盈利多少，并且接待盡量多的客人。

解題思路：将客人按照消費金額、人數排序，然後桌子按照從小到大排序。消費高的客人盡量找最小滿足的桌子給他們。注意輸出的時候客人有序号，桌子同樣有序号，不能打亂。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 1005;
struct state {
	int id, val, sum;
	state () {
	}
}g[N], t[N];
int n, m, v[N];

bool cmpS (const state& a, const state& b) {
	if (a.val != b.val) return a.val > b.val;
	return a.sum > b.sum;
}

bool cmpT (const state& a, const state& b) {
	return a.sum < b.sum;
}

void init () {
	memset(v, 0, sizeof(v));

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &g[i].sum, &g[i].val);
		g[i].id = i;
	}

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &t[i].sum);
		t[i].id = i;
	}

	sort(g, g + n, cmpS);
	sort(t, t + m, cmpT);
}

void solve () {
	int ans = 0, cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i].sum <= t[j].sum) {
				cnt++;
				ans += g[i].val;
				v[g[i].id] = t[j].id + 1;
				t[j].sum = 0;;
				break;
			}
		}
	}
	printf("%d %d\n", cnt, ans);
	for (int i = 0; i < n; i++) {
		if (v[i]) printf("%d %d\n",	i + 1, v[i]);
	}
}

int main () {
	init ();
	solve ();
	return 0;
}