A30361. 算法学习
填空题
困难
知识点
题目描述
算法学习
题目描述
小杨计划学习 m 种算法，为此他找了 道题目来帮助自己学习，每道题目至多学习一次。
小杨对于 m 种算法的初始掌握程度均为 。第 i 道题目有对应的知识点 ai，即学习第i道题目可以令小杨对第 ai 种算法的掌握程度提高 bi。小杨的学习目标是对 m 种算法的掌握程度均至少为 k。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。
输入格式
第一行三个正整数 m,n,k，代表算法种类数，题目数和目标掌握程度。
第二行n个正整数a1,a2,,,,an，代表每道题目的知识点。
第二行n个正整数b1,b2,,,,bn，代表每道题目提升的掌握程度。
输出格式
输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 -1。
输入样例1
3 5 10
1 1 2 3 3
9 1 10 10 1输出样例1
4输入样例2
2 4 10
1 1 1 2
1 2 7 10输出样例2
-1对于样例1，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int f[N];
vector<int> score[N + 2], a, b;
bool cmp(int i, int j) {
return i > j;
}
int main() {
int n, m, k;
cin >> m >> n >> k;
a.resize(n), b.resize(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++) {
cin >> b[i];
score[a[i]].emplace_back(b[i]);
}
vector<int> need(m + 2);
int ans = 0, mx_meed = 0, mx_need_i = -1;
for (int i = 1; i <= m; i ++) {
sort(score[i].begin(), score[i].end(), cmp);
int sum = 0;
for (int j = 0; j < (int) score[i].size(); j ++) {
sum += score[i][j];
if (sum >= k) {
need[i] = j + 1;
break ;
}
}
if (sum < k) {
puts("-1");
return 0;
}
ans += need[i];
if (need[i] > mx_meed)
mx_meed = need[i], mx_need_i = i;
}
if (mx_meed - 1 <= ans - mx_meed) {
cout << ans << endl;
return 0;
}
int last = 0;
for (int i = 1; i <= m; i ++)
if (i != mx_need_i)
last += score[i].size() - need[i];
cout << (mx_meed - 1 <= ans - mx_meed + last ? 2 * mx_meed - 1 : -1) << endl;
return 0;
}
上一题
下一题