[语言月赛202306] 演唱会 题解

· · 题解

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 首。
}

视频题解