4649: 【GESP2409六级】算法学习

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

习$m$ 种算法，为此他找了$n$ 道题目来帮助自己学习，每道题目至多学习一次。
小杨对于$m$ 种算法的初始掌握程度均为$0$ 。第 道题目有对应的知识点$a_i$ ，即学习第$i$ 道题目可以令小杨对第$a_i$ 种算法的掌握程度提高$b_i$ 。小杨的学习目标是对$m$ 种算法的掌握程度均至少为$k$ 。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

输入

第一行三个正整数$m,n,k$ ，代表算法种类数，题目数和目标掌握程度。
第二行 个正整数$a_1,a_2,...,a_n$ ，代表每道题目的知识点。
第二行 个正整数 $b_1,b_2,...,b_n$，代表每道题目提升的掌握程度。

输出

输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 $-1$。

样例输入 复制 

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

样例输出 复制 

4

提示

#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;
}

来源/分类

提交提交记录统计露一手!