P9942 [USACO21JAN] Just Stalling B Solution

OIerWu_829 · 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;
}