蓝桥杯入门赛【舞狮】算法赛题目
题目问题描述
舞狮是中国传统民间艺术，起源于汉代，盛行于唐代。它结合了武术、舞蹈和音乐，常在节日和庆典中表演，象征驱邪避灾、带来好运。表演者通过模仿狮子的动作，展现狮子的喜怒哀乐，常伴有锣鼓音乐，增添喜庆氛围。
假如一支舞狮队中，从狮头开始，每位成员的舞狮技能值严酷大于其前面全部成员的数量，那么这支舞狮队被称为公道的舞狮队。例如 [1,2
,3,4],[2
,3,5][1,2
,3,4],[2
,3,5] 是合法的舞狮队，,[2
,1,3],[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] 和 ，至少必要分成两支舞狮队。
运行限制
语言最大运行时间最大运行内存C++1s2
56MC1s2
56MJava2
s2
56MPython33s2
56MPyPy33s2
56MGo3s2
56MJavaScript3s2
56M 代码展示
#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;
}
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 的大小即为最少必要的队列数目。
写者心得
那我解决这个题目的时候，我的第一反应就是通过排序，然后查找符合要求的数组，然后记次数，但是后面颠末学习，发觉这个题应该利用贪婪算法再加上二分查找，可以更高效的解决这个问题，其中还用到了优先队列算法，可以说是一个复合题目难度对于我来说的确不低，其中利用的这个函数也是我不曾用过的
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]