题解：P1056 [NOIP2008 普及组] 排座椅

solution

贪心和模拟。

要求上课时交头接耳的学生对数最少，转化成求通道能阻断的学生对数最多。

题目保证给出的

D

对同学都是左右或前后相邻，若左右相邻，需要在列上间隔，若前后相邻，需要在行上间隔。由此，我们可以统计出每行能阻断的对数，我们选出前

K

多的行，将这些行按从大到小输出，列是同理的。

通过记录。

code

CPP

#include <bits/stdc++.h>
using namespace std;
int n, m, k, l, d, K[1005], L[1005], ans[1005];
pair<int, int> a[1005];
void solve (int x, int b[], int num) {
	ans[0]=0;
	for (int i=1; i<=x; ++i)
		a[i]={b[i], i};
	sort(a+1, a+x+1);
	for (int i=x; i>=x-num+1; --i)
		ans[++ans[0]]=a[i].second;
	sort(ans+1, ans+num+1);
	for (int i=1; i<=num; ++i)
		cout << ans[i] << ' ';
}
int main () {
	cin >> n >> m >> k >> l >> d;
	for (int i=1, x, y, p, q; i<=d; ++i) 
		cin >> x >> y >> p >> q,
		x==p?L[min(y, q)]++:K[min(x, p)]++;
	solve(n, K, k);
	cout << '\n';
	solve(m, L, l);
	return 0;
}

题解：P1056 [NOIP2008 普及组] 排座椅

文章操作

solution

code

相关推荐

评论

题解：P1056 [NOIP2008 普及组] 排座椅