题解：P11247 [GESP202409 六级] 算法学习

· · 题解

2025/4/24：改正了评论里提出的一些代码错误。

2025/5/30：再次改正了评论中提出的一些代码和思路错误。

2025/8/19：再次改正了评论中提出的一些代码和思路错误。

（数据过水）（数据过水）

思路

显然，对于每个知识点做能得到更多经验值的题目更优。

这样，我们可以用一个 pair 来存储这道题的经验值，这道题的知识点，进行排序，这样系统默认第一个元素为第一关键字，第二个元素为第二关键字，从小到大排序。

然后，就要开始选择题目。从 n 枚举到 1，如果第 i 道题的知识点还没有达到 k，就要做这道题，因此我们需要用一个数组 b 来存储第 i 个知识点的经验值，ans 存储选择的题目数量。还要用数组 c 存储每个知识点选了多少道题，用于计算选择题数最高的知识点选择的题数，用 maxn 存储，用处稍后会讲到。

当有任何一个知识点还没有达到 k，输出 -1。

由于题目说：连续做同样知识点的题是不好的，这样选择题数最高的知识点是应该重点考虑的，当 maxn 超过了 \lceil\frac{n}{2}\rceil，无论按什么顺序做题都会使连续做两道同样知识点的题，这时也得输出 -1。

如果要保证不会连续做两道同样知识点的题，需要保证 maxn\times 2-1\le n（注意：这里不是 maxn\le \lceil \frac{ans}{2}\rceil，因为可以去随便多做一些题以满足这一条件，但至少要做的题目总数不可以超过 n），这样子就可以交叉做题，因此答案为 \max(ans,maxn\times 2-1)。

注意：要存储选择了最多题的知识点总题数，以免没有足够的题去乱做，使无法让两道同样知识点的题不一起做。

例如：

2 6 10
1 1 1 1 1 2
5 3 2 1 1 10

这样一定要选的是 3 个知识点一，1 个知识点二，然而，剩下的题都是知识点一，即没有足够的题去乱做，输出 -1。

代码：

#include<bits/stdc++.h>
using namespace std;
int m,n,k,b[100001],c[100001],anss,ans,maxn,maxk=1e9,ti[100001];
pair<int,int>a[100001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].second;
        ti[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){
            b[a[i].second]+=a[i].first;//统计现在的经验值 
            if(b[a[i].second]>=k)anss++;//统计有多少个知识点达到了k 
            ans++;//增加题数 
            c[a[i].second]++;//统计每个知识点的选择题数 
            if(maxn<c[a[i].second])maxn=c[a[i].second],maxk=ti[a[i].second];//统计选择最多题的知识点选择了的题数 
            else if(maxn==c[a[i].second])maxk=min(ti[a[i].second],maxk);
            //另外 maxk 存储选择了最多题的知识点总题数，以免没有足够的题去乱做，使无法让两道同样知识点的题不一起做。 
        }
    }if(anss!=m||maxn*2-1>n||maxn>n-maxk)cout<<"-1";//输出 
    else cout<<max(maxn*2-1,ans);
    return 0;
}

注：一组 hack 数据（评论区中提出的，可以 hack 掉一部分题解）：

2 9 7
2 2 1 1 1 2 1 1 1
1 3 1 9 2 3 9 7 8
output: 5