算法学习

题目描述

⼩杨计划学习 种算法，为此他找了 道题⽬来帮助⾃⼰学习，每道题⽬⾄多学习⼀次。 ⼩杨对于 种算法的初始掌握程度均为 。第 道题⽬有对应的知识点 ，即学习第 道题⽬可以令⼩杨对第 种 算法的掌握程度提⾼ 。⼩杨的学习⽬标是对 种算法的掌握程度均⾄少为 。 ⼩杨认为连续学习两道相同知识点的题⽬是不好的，⼩杨想请你编写程序帮他计算出他最少需要学习多少道题⽬才 能使得他在完成学习⽬标的同时避免连续学习两道相同知识点的题⽬。

输入格式

第⼀⾏三个正整数 ，代表算法种类数，题⽬数和⽬标掌握程度。 第⼆⾏ 个正整数 ，代表每道题⽬的知识点。 第⼆⾏ 个正整数 ，代表每道题⽬提升的掌握程度。

输出格式

输出⼀个整数，代表⼩杨最少需要学习题⽬的数量，如果不存在满⾜条件的⽅案，输出 -1。 3.2.4 样例1 1 3 5 10 2 1 1 2 3 3 3 9 1 10 10 1 1 4 3.2.5 样例2 1 2 4 10 2 1 1 1 2 3 1 2 7 10 1 -1 对于样例1，⼀种最优学习顺序为第⼀道题，第三道题，第四道题，第⼆道题。 子任务编号 数据点占比 1 30% 2 30% 3 40% 对于全部数据，保证有 。 3.2.6 参考程序 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5 + 5; 4 const int inf = 0x3f3f3f3f; 5 int f[N]; 6 vector score[N + 2], a, b; 7 bool cmp(int i, int j) { 8 return i > j; 9 } 10 int main() { 11 int n, m, k; 12 cin >> m >> n >> k; 13 a.resize(n), b.resize(n); 14 for (int i = 0; i < n; i ++) 15 cin >> a[i]; 16 for (int i = 0; i < n; i ++) { 17 cin >> b[i]; 18 score[a[i]].emplace_back(b[i]); 19 } 20 21 vector need(m + 2); 22 int ans = 0, mx_meed = 0, mx_need_i = -1; 23 for (int i = 1; i <= m; i ++) { 24 sort(score[i].begin(), score[i].end(), cmp); 25 int sum = 0; 26 for (int j = 0; j < (int) score[i].size(); j ++) { 27 sum += score[i][j]; 28 if (sum >= k) { 29 need[i] = j + 1; break ; 30 } 31 } 32 if (sum < k) { 33 puts("-1"); return 0; 34 } 35 ans += need[i]; 36 if (need[i] > mx_meed) 37 mx_meed = need[i], mx_need_i = i; 38 } 39 if (mx_meed - 1 <= ans - mx_meed) { 40 cout << ans << endl; 41 return 0; 42 } 43 44 int last = 0; 45 for (int i = 1; i <= m; i ++) 46 if (i != mx_need_i) 47 last += score[i].size() - need[i]; 48 49 cout << (mx_meed - 1 <= ans - mx_meed + last ? 2 * mx_meed - 1 : -1) << endl; 50 return 0; 51 }

样例输入 #1

1 3 5 10
2 1 1 2 3 3
3 9 1 10 10 1
1 4

样例输出 #1

样例输入 #2

1 2 4 10
2 1 1 1 2
3 1 2 7 10
1 -1
对于样例1，⼀种最优学习顺序为第⼀道题，第三道题，第四道题，第⼆道题。
子任务编号 数据点占比
1 30%
2 30%
3 40%

样例输出 #2

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。