题目
问题描述
舞狮是中国传统民间艺术，起源于汉代，盛行于唐代。它结合了武术、舞蹈和音乐，常在节日和庆典中表演，象征驱邪避灾、带来好运。表演者通过模仿狮子的动作，展现狮子的喜怒哀乐，常伴有锣鼓音乐，增添喜庆氛围。
如果一支舞狮队中，从狮头开始，每位成员的舞狮技能值严格大于其前面所有成员的数量，那么这支舞狮队被称为合理的舞狮队。例如 [1,2,3,4],[2,3,5][1,2,3,4],[2,3,5] 是合法的舞狮队，[1,3,1],[2,1,3][1,3,1],[2,1,3] 则不是合法的舞狮队。
新年即将到来，蓝桥村今年的舞狮队共有 NN 名成员，第 ii 名成员的舞狮技能值为 AiAi。舞狮队教练小蓝需要将这 NN 名成员合理地分组形成舞狮队，他想知道最少需要分成多少队，请你帮忙解决这个问题。
注意：你必须保证每位成员至少被分到一个舞狮队。
输入格式
第一行输入一个整数 N(1≤N≤105)N(1≤N≤105) 表示舞狮队成员的数量。
第二行输入 NN 个整数 A1,A2,A3,⋯,AN(1≤Ai≤N)A1,A2,A3,⋯,AN(1≤Ai≤N) 表示每位成员的舞狮技能值。
输出格式
输出一个整数表示答案。
样例输入
5
1 3 5 2 1
样例输出
2
说明
对于样例，可以分为 [1,2,3][1,2,3] 和 [1,5][1,5]，至少需要分成两支舞狮队。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 2s | 256M |
| Python3 | 3s | 256M |
| PyPy3 | 3s | 256M |
| Go | 3s | 256M |
| JavaScript | 3s | 256M |
代码展示
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}sort(a.begin(), a.end());multiset<int> s;for (int x : a) {auto it = s.lower_bound(x);if (it == s.begin()) {s.insert(1);} else {--it;int k = *it;s.erase(it);s.insert(k + 1);}}cout << s.size() << endl;return 0;
}代码解释
-
输入处理：读取输入数据并存储在一个向量中。
-
排序：对向量进行升序排序，以便按顺序处理每个成员。
-
维护队列长度：使用多重集合
s来维护当前所有队列的长度。 -
处理每个成员：
-
使用
lower_bound查找第一个不小于当前成员技能值的位置。 -
如果没有找到合适的队列（即所有队列的长度都不小于当前成员技能值），则新建一个队列。
-
否则，将当前成员放入找到的最长队列中，并更新该队列的长度。
-
-
输出结果：最终，集合
s的大小即为最少需要的队列数目。
写者心得
那我解决这个题目的时候，我的第一反应就是通过排序，然后查找符合要求的数组，然后记次数，但是后面经过学习，发觉这个题应该使用贪心算法再加上二分查找，可以更高效的解决这个问题，其中还用到了优先队列算法，可以说是一个复合题目难度对于我来说的确不低，其中使用的这个函数也是我不曾用过的
