G6010 [GESP202409 六级] 算法学习 题解

知识点：贪心、分组排序、调度可行性。

解题思路

每个知识点内按收益降序，求达到k的最少题数c_i，记sum和最大值maxneed。总题数至少max(sum,2maxneed-1)，并检查最大组之外是否至少有maxneed-1道可用题作间隔。

为什么正确

各组降序使达到目标所需题数最小；最大组相邻题之间必须插入其他组题，数量下界和总可用间隔共同决定可行性。

易错点

其他组额外题也可以作为间隔；任一组收益总和不足k直接输出-1。

复杂度

时间O(n log n+m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n,k;
    cin>>m>>n>>k;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    vector<vector<int>>g(m+1);
    for(int i=0;i<n;i++) {
        int b;
        cin>>b;
        g[a[i]].push_back(b);
    }
    int sum=0,maxneed=0,dom=0;
    for(int i=1;i<=m;i++) {
        sort(g[i].rbegin(),g[i].rend());
        int s=0,c=0;
        for(int x:g[i]) {
            if(s>=k)break;
            s+=x;
            c++;
        }
        if(s<k) {
            cout<<-1;
            return 0;
        }
        sum+=c;
        if(c>maxneed) {
            maxneed=c;
            dom=i;
        }
    }
    if(n-(int)g[dom].size()<maxneed-1)cout<<-1;
    else cout<<max(sum,2*maxneed-1);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。