自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:15:01，当前版本为作者最后更新于2023-06-08 20:10:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Source & Knowledge

2023 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

有 $a$ 名同学与 $n$ 首歌，给出每位同学从每首歌中获得的快乐值，按照给予的总快乐值即欢乐度从高到低排序，选出前 $m$ 首，并特殊处理她最喜欢的歌，求出最终的歌单。

题目分析

本题考察结构体与简单排序。

首先，我们先考虑，排除掉 「她」 的限制，可以发现，只需要开一个数组记录每首歌的欢乐度，这个可以在输入时累加，然后从大到小排序，找出前 $m$ 首歌就行了。可以用选择排序或者冒泡排序，同时记录编号。或者可以采用结构体排序，用一个结构体记录两个信息：欢乐度和编号，然后使用 sort，按欢乐度从大到小排序，像这样：

struct song{
	int id,k;//id 表示编号，k 表示欢乐度
}h[100010];

bool cmp(song a,song b){
	return a.k > b.k;//按照欢乐度从大到小排列
}

sort(h+1,h+n+1,cmp);//使用 sort 函数

现在再来考虑加上了「她」的限制该怎么做。

首先，记录她最喜欢歌的编号。这很简单，只需要在学号为 b 时，使用一个变量 $ex$ 记录收货快乐值最多的歌的编号。

然后就是判断了。在排好序后，我们先在前 $m$ 首歌中找一遍，看看有没有她最喜欢的歌。如果没有，就先输出前 $m-1$ 首歌的编号，再输出 $ex$，这就达到了删去最后一首歌，并把她最喜欢的歌放在最后的效果。如果有，那就先输出 $ex$，然后依次输出前 $m$ 首歌的编号，但碰到 $ex$ 时，就直接跳过，这样就达到了把她最喜欢的歌提到歌单的第一个位置，其它歌相对位置不变的效果。至此，这题也就完成了。还要注意，由于 $a$ 可能达到 $100$，$n$ 可能达到 $10^5$，输入量可能会达到 $10^7$，所以保险起见，使用格式化输入，以防超时。核心代码如下：

struct song{
	int id,k;
}h[100005];
bool cmp(song a,song b){
	return a.k>b.k;
}



for(int i=1;i<=a;i++){
	for(int j=1;j<=n;j++){
		int x;
		scanf("%d",&x);//格式化输入
		h[j].k+=x,h[j].id=j;//别忘了把 id 也赋好值
		if(i==b&&x>k)ex=j,k=x;//处理她最喜欢的歌，k记录目前快乐值的最大值，注意与结构体中的 k 区分
	}
}
sort(h+1,h+n+1,cmp);//排序
bool f=0;//判断ex是否在歌单里
for(int i=1;i<=m;i++)if(ex==h[i].id)f=1;
if(f){
	printf("%d ",ex);//在歌单里，先输出ex
	for(int i=1;i<=m;i++)if(h[i].id!=ex)printf("%d ",h[i].id);//记得跳过 ex。
}
else {
	for(int i=1;i<m;i++)printf("%d ",h[i].id);
	printf("%d",ex);//不在歌单里，先输出前 m-1 首。
}

视频题解