4.2 KiB
4.2 KiB
一、算法选择
显然，对于每个知识点做能得到 更多经验值的题目更优。
所以，基本上认为是：【贪心】
二、基本思路
既然定位是贪心，那么 一般的套路就排序，然后从大到小选择。
用一个 PII 来存储每道题的 ① 经验值，② 知识点，按经验值进行排序，这样系统默认第一个元素为第一关键字，第二个元素为第二关键字，默认是从小到大排序，一会遍历的时候需要倒序进行。
从 n 枚举到$1$，如果第 i 道题的知识点还没有达到 $k$，就要做这道题:
- ① 数组
b保存每个知识点的 已经取得的经验值 - ② 数组
c保存每个知识点的 选择题数 - ③ 变量
ans保存答案，也就是一共选择了多少道题 - ④ 变量
cnt保存 达标了的知识点数量 - ⑤ 变量
mx保存选择题数最高的知识点选择的题数 【下面会讲解为什么要保留这个变量】
思考： 问：为什么会想到记录上面这些变量呢？ 答：因为我们不管题目最终想要计算什么，事情发生过程中，客观记录事实最重要，有啥都记录下来总没错。
三、结果判定
本题最难想的就是结果的判定，因为它有一个要求：连续做两道同样知识点的题是不好的。 我们可以举例子思考可能的所有情况有哪些：
① 一共一个知识点，第一个知识点需要$50$点经验,结果相关联的题目经验值加在一起最多也不到$50$点，此时，输出$-1$。
② 一共两个知识点，第一个知识点需要经验值最高的前$4$道题，第二个知识点需要经验值最高的前$3$道题 ，此时，会发生什么呢？我们会发现，这时候直接输出$4+3=7$就行了。
③ 一共两个知识点，第一个知识点需要经验值最高的前$5$道题，第二个知识点需要经验值最高的前$3$道题 ，此时，会发生什么呢？我们会发现，这时候直接输出$8$是不行的，因为$5$道题，中间最少是$4$个空，现在只有$3$个可以用来间隔的，缺少一个。为什么与 ② 时情况不同呢？就是因为最多的太多了，需要照顾最多的，给它插好空，也就是$mx*2-1$。
④ 继续上面 ③的思考过程 ，那如果总的题目数量也不够$mx*2-1$，此时，输出$-1$。
四、代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m; // 算法种类数
int n; // 题目数
int k; // 目标掌握程度
int b[N]; // 代表每道题目已经取得的经验值
pair<int, int> a[N]; // 代表每道题目的frist:经验值,second:知识点
int c[N]; // 存储每个知识点选了多少道题
int cnt, ans, mx;
int main() {
cin >> m >> n >> k; // 输入算法种类数,题目数,目标掌握程度
for (int i = 1; i <= n; i++)
cin >> a[i].second; // 输入每道题目的知识点
for (int i = 1; i <= n; i++)
cin >> a[i].first; // 输入学习每道题目可以获取到的经验值
sort(a + 1, a + n + 1); // 按可以获取到的经验值最小到大排序
for (int i = n; i >= 1; i--) { // 倒序枚举，就是经验值最大到小
if (b[a[i].second] < k) { // 第a[i].second,也就是该知识点的已获得的经验值不够k
b[a[i].second] += a[i].first; // 这道题需要做一下，经验值增加
if (b[a[i].second] >= k)
cnt++; // 有多少个知识点达到了k
ans++; // 增加题数(记录使了多少个题目)
c[a[i].second]++; // 统计每个知识点的选择题数
mx = max(mx, c[a[i].second]); // 统计选择最多题的知识点选择了的题数
}
}
// ① 如果最终可以达标的算法数量不够m个，表示无解
// ② 如果选择最多的题数大于题目总数的一半，表示无解
if (cnt < m || n < mx * 2 - 1)
cout << -1 << endl; // 输出-1
else
cout << max(mx * 2 - 1, ans) << endl; // 输出最大值
return 0;
}