自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:53:13，当前版本为作者最后更新于2023-12-27 15:50:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

贪心策略：优先给高度高的奶牛安排牛棚。

先遍历每头牛，计算其可安排的牛棚数，乘到方案总数 $ans$ 中。

再遍历每个牛棚，统计可安排第 $i$ 头牛的牛棚数 $cnt$。

但前 $i-1$ 头牛已经安排了 $i-1$ 个牛棚，所以 $cnt$ 需要减去 $i-1$。

#include <iostream>
#include <algorithm>
using namespace std;
int a[30], b[30];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	sort(a + 1, a + 1 + n, greater<int>()); // 从大到小排序
	long long ans = 1;
	for (int i = 1; i <= n; i++) {
		int cnt = 0; // 计算每头牛可分配的牛棚数量
		for (int j = 1; j <= n; j++)
		    if (b[j] >= a[i]) cnt++;
		cnt -= (i - 1);
		ans *= cnt;
	}
	cout << ans << endl;
	return 0;
}