题意分析

John Doe 是一位 DJ，他需要将一组歌曲录制在磁带上，以最小化预期访问时间。每首歌曲有三个属性：

1. 标识符：唯一标识歌曲。
2. 长度：歌曲的播放时长。
3. 频率：歌曲被播放的频率。

目标是将歌曲按照某种顺序排列，使得以下公式最小化：

$$\sum_{i=1}^{n} f_{S_i} \cdot \sum_{j=1}^{i} l_{S_j} $$

其中：

• $f_{S_i}$ 是第 $i$ 首歌曲的频率。
• $l_{S_j}$ 是第 $j$ 首歌曲的长度。

解题思路

1. 公式理解：

   • 公式的第一部分 $\sum_{i=1}^{n} f_{S_i}$ 表示所有歌曲的频率之和。
   • 公式的第二部分 $\sum_{j=1}^{i} l_{S_j}$ 表示前 $i$ 首歌曲的长度之和。
   • 因此，公式可以理解为：每首歌曲的频率乘以其前面所有歌曲的长度之和的总和。

2. 优化目标：

   • 需要找到一种歌曲排列顺序，使得上述公式的值最小。

3. 贪心策略：

   • 通过观察可以发现，将 频率高且长度短 的歌曲放在前面，可以最小化公式的值。
   • 因此，我们可以定义一种排序规则：按照 $\frac{f_i}{l_i}$ 从大到小排序。

4. 实现步骤：

   • 读取输入数据，存储每首歌曲的标识符、长度和频率。
   • 按照 $\frac{f_i}{l_i}$ 从大到小对歌曲进行排序。
   • 根据排序后的顺序，找到指定位置的歌曲标识符并输出。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Song {
    int id;       // 歌曲标识符
    int length;   // 歌曲长度
    double freq;  // 歌曲频率
};

// 比较函数，按照 f_i / l_i 从大到小排序
bool compare(const Song& a, const Song& b) {
    double ratioA = a.freq / a.length;
    double ratioB = b.freq / b.length;
    return ratioA > ratioB;
}

int main() {
    int N;
    while (cin >> N && N != 0) {
        vector<Song> songs(N);
        for (int i = 0; i < N; ++i) {
            cin >> songs[i].id >> songs[i].length >> songs[i].freq;
        }

        // 按照 f_i / l_i 从大到小排序
        sort(songs.begin(), songs.end(), compare);

        int S;
        cin >> S;  // 读取需要查询的位置

        // 输出第 S 首歌曲的标识符（注意：位置从 1 开始）
        cout << songs[S - 1].id << endl;
    }
    return 0;
}

代码解释

1. 数据结构：

   • 使用 struct Song 存储每首歌曲的标识符、长度和频率。

2. 排序规则：

   • 定义 compare 函数，按照 $\frac{f_i}{l_i}$ 从大到小排序。

3. 输入处理：

   • 读取歌曲数量 $N$，然后读取每首歌曲的信息。
   • 按照排序规则对歌曲进行排序。

4. 输出结果：

   • 读取查询位置 $S$，输出排序后第 $S$ 首歌曲的标识符。

---

复杂度分析

1. 时间复杂度：
   • 排序的时间复杂度为 $O(N \log N)$，其中 $N$ 是歌曲数量。
2. 空间复杂度：
   • 需要 $O(N)$ 的空间存储歌曲信息。

---