CodeForces-388A 题解

发表于2023-07-14更新于2023-07-14

题目传送门

一道贪心题……

我们先将箱子的力量值从小到大排序，优先将小的放顶上，只要还能在底下放就放，否则就到下一个堆。

为什么要从小到大往下放呢？因为越小的力量值能放的位置就越少，所以尽早放一定是最优的。相反，力量值大的选择更多。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, ans;
int a[105];
bool vis[105]; // vis[i] = 1 表示这个箱子已经用过了
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        int cnt = 1; // 当前最顶上有 1 个
        for (int j = i + 1; j <= n; j++) {
            if (!vis[j] and cnt <= a[j])  {
                vis[j] = 1;
                cnt++;
            }
        }
        ans++;
    }
    cout << ans;
    return 0;
}