自动搬运

查看原文

来自洛谷，原作者为

	Eddie08012025 减训减训

搬运于2025-08-24 23:05:41，当前版本为作者最后更新于2024-11-13 09:08:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

思路

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

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

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

当有任何一个知识点还没有达到 $k$，输出 -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||maxn2-1>n||maxn>n-maxk)cout<<"-1";//输出 else cout<<max(maxn2-1,ans); return 0; } 的题是不好的，这样选择题数最高的知识点是应该重点考虑的，当 $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