如果声音不记得

览遍千秋 · 2024-08-21 23:07:26 · 题解

Source & Knowledge

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

考察二维数组、简单构造。

文字题解

共有 n 首歌曲，m 类题材，容易算出每类题材有 k=\dfrac{n}{m} 首歌。

如何得到一个符合题意的序列？首先，我们需要按照题材将歌曲的编号分别存储下来。

如何存储？我们将利用一个一维数组 w[] 和一个二维数组 s[][]。w[i] 表示当前第 i 类题材已经有几首歌曲了，s[i][] 用于存储第 i 类歌曲的编号。

当输入了第 i 首歌曲的编号 c_i，我们需要把编号 i 归入第 c_i 类，需要进行以下的操作：

• 将 c_i 类的歌曲数目增加 1，也就是 w[c_i] 增加 1
• 将 i 存入 s[c_i][w[c_i]]

分类存储完后，我们可以按照如下的策略安排播放顺序：

• 播放第 1 种题材的第 1 首
• 播放第 2 种题材的第 1 首
• ……
• 播放第 m 种题材的第 1 首
• 播放第 1 种题材的第 2 首
• 播放第 2 种题材的第 2 首
• ……
• 播放第 m 种题材的第 2 首
• ……
• 播放第 1 种题材的第 k 首
• 播放第 2 种题材的第 k 首
• ……
• 播放第 m 种题材的第 k 首

这可以通过按照先列后行对 s 数组进行遍历完成：

for(int i = 1; i <= k; i++) {
    for(int j = 1; j <= m; j++) {
        cout << s[j][i] << endl;
    }
}

视频题解