P9942 [USACO21JAN] Just Stalling B 题解

GMOJ
洛谷

大意

$FJ$ 有 $N$ 头奶牛，给你第 $i$ 头奶牛的高度，现在要把它们安排到 $N$ 个牛棚中，每个牛棚有高度限制，高度大于这个限制的奶牛不能被安排到这个牛棚中。

现在告诉你每个牛棚的高度限制和每头奶牛的高度，求满足条件的安排方案数。

解法

明显满足乘法原理。

我们先把高度大的奶牛安排了，才能去安排小的，所以一开始先从大到小排序。设第 $i$ 个奶牛可以入住的牛棚数量为 $S_i$（不考虑别的奶牛），每个奶牛实际可以选择的牛棚 $T_i$ 为

$$T_i=S_i-t$$

$t$ 为之前已经安排的奶牛的数量。

那么答案 $ans$ 为：

$$ans=\prod_{i=1}^NT_i$$

#include <bits/stdc++.h>
using namespace std;
int n,a[100],b[100],c[100];
int main()
{
	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+n+1);
	bool f=1;
	for (int i = 1 ; i <= n ; ++i)
	{
		for (int j = 1 ; j <= n ; ++j)
		{
			if (a[i]<=b[j]) c[i]++;
		}
		if (c[i]) f=0;
	}
	if (f)
	{
		cout << 0 << endl;
		return 0;
	}
	long long ans=1;
	for (int i = 1 ; i <= n ; ++i)
	{
		ans*=c[n-i+1]-i+1;
	}
	cout << ans << endl;
	return 0;
}