题目大意

有

m

种算法，初始掌握度均为零，有

n

道题用来辅助提高掌握度（每一道题目只会对应提高一个算法），要求在不连续学习两道对应算法相同的题目的情况下使

m

种算法掌握度均提高至

k

以上，最少需学习几题，如果无法完成上述条件，输出负一。

分析

这是一道贪心题，输入后先按每道题目能增加的掌握度从大到小排序。之后便利

n

道题目，如该题对应算法掌握度已达标，就跳过，否则该题对应算法掌握度就加上学习该题可以增加的算法掌握度。

注意

还要用两个数组分别记录该算法掌握度和学习了几道对应此算法的题目，如果学习了几道对应此算法的题目数量大于一共学习题目数量的一半，那就输出负一。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long m,n,k,f[100005],d[100005],sum,ans;//定义
struct node{
	long long s,w;
}a[100005];//题目对应算法和提高掌握度值用结构体保存
bool cmp(node i,node j)
{
	return i.w>j.w;
}//排序
int main()
{
	cin>>m>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i].s;
	for(int i=1;i<=n;i++) cin>>a[i].w;
	sort(a+1,a+n+1,cmp);//排序
	for(int i=1;i<=n;i++)
	{
		if(f[a[i].s]>=k) continue;//如果无需学习，那么跳过
		else
		{
			f[a[i].s]+=a[i].w;//算法掌握度加上该题提高量
			d[a[i].s]++;//记录该算法学了几题
			sum++;//所有算法学习题目量+1
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(d[i]>sum-d[i]+1||f[i]<k)
		{
			cout<<-1;
			return 0;
		}//如果该算法学习题目数量大于总学习题目数量，或学了所有该题算法也无法达标，输出负一
	}
	cout<<sum;
}

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

文章操作

题目大意

分析

注意

代码

相关推荐

评论

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