UVa 1346 Songs

题目描述

John Doe\texttt{John Doe}John Doe是一位著名的DJ\texttt{DJ}DJ，他需要优化磁带中歌曲的排列顺序。对于给定的磁带和每首歌曲，已知歌曲的长度和播放频率。目标是将歌曲按照某种顺序录制在磁带上，使得期望访问时间最小。

如果歌曲按照顺序Ss(1),Ss(2),…,Ss(n)S_{s(1)}, S_{s(2)}, \ldots, S_{s(n)}Ss(1)​,Ss(2)​,…,Ss(n)​录制在磁带上，那么需要最小化的函数是：

∑i=1nfs(i)∑j=1ils(j)\sum_{i=1}^{n} f_{s(i)} \sum_{j=1}^{i} l_{s(j)}i=1∑n​fs(i)​j=1∑i​ls(j)​

其中：

• fs(i)f_{s(i)}fs(i)​是第iii首歌曲的播放频率
• ls(j)l_{s(j)}ls(j)​是第jjj首歌曲的长度

输入格式

程序输入来自文本文件，每个数据集包含：

• 歌曲数量NNN（161616位整数）
• NNN行歌曲规格，每行包含：歌曲标识符（整数）、长度（161616位整数）、播放频率（浮点数）
• 一个数字，表示歌曲SSS在优化后磁带上的位置

输出格式

对于每个数据集，输出优化后磁带上第SSS首歌曲的标识符。

题目分析

问题理解

我们需要找到一种歌曲排列顺序，使得期望访问时间最小。期望访问时间的计算公式为：

期望访问时间=∑i=1nfi×(前 i 首歌曲的总长度)\text{期望访问时间} = \sum_{i=1}^{n} f_i \times (\text{前 $i$ 首歌曲的总长度})期望访问时间=i=1∑n​fi​×(前i首歌曲的总长度)

这意味着：

• 每首歌曲的访问时间等于它前面所有歌曲的长度之和（包括自身）
• 总的期望访问时间是每首歌曲的播放频率乘以其访问时间的总和

关键洞察

这个问题本质上是一个调度优化问题。为了最小化总的期望访问时间，我们需要确定歌曲的最佳排列顺序。

通过分析可以发现，这个问题与操作系统中的磁盘调度算法或任务调度问题有相似之处。最优策略是按照单位长度频率（频率与长度的比值）的降序排列歌曲。

贪心策略证明

假设有两首相邻的歌曲AAA和BBB，其中：

• 歌曲AAA：长度为lAl_AlA​，频率为fAf_AfA​
• 歌曲BBB：长度为lBl_BlB​，频率为fBf_BfB​

如果AAA在BBB前面，它们对总成本的贡献为：
fA×lA+fB×(lA+lB)f_A \times l_A + f_B \times (l_A + l_B)fA​×lA​+fB​×(lA​+lB​)

如果BBB在AAA前面，贡献为：
fB×lB+fA×(lA+lB)f_B \times l_B + f_A \times (l_A + l_B)fB​×lB​+fA​×(lA​+lB​)

两种顺序的成本差为：
[fA×lA+fB×(lA+lB)]−[fB×lB+fA×(lA+lB)]=fB×lA−fA×lB[f_A \times l_A + f_B \times (l_A + l_B)] - [f_B \times l_B + f_A \times (l_A + l_B)] = f_B \times l_A - f_A \times l_B[fA​×lA​+fB​×(lA​+lB​)]−[fB​×lB​+fA​×(lA​+lB​)]=fB​×lA​−fA​×lB​

为了使AAA在BBB前面更优，需要：
fB×lA−fA×lB<0⇒fAlA>fBlBf_B \times l_A - f_A \times l_B < 0 \Rightarrow \frac{f_A}{l_A} > \frac{f_B}{l_B}fB​×lA​−fA​×lB​<0⇒lA​fA​​>lB​fB​​

因此，按照fili\frac{f_i}{l_i}li​fi​​的降序排列是最优策略。

算法步骤

1. 读取歌曲数量NNN
2. 读取NNN首歌曲的信息（标识符、长度、频率）
3. 按照频率长度\frac{\text{频率}}{\text{长度}}长度频率​的比值对歌曲进行降序排序
4. 读取目标位置SSS
5. 输出排序后列表中第SSS首歌曲的标识符

复杂度分析

• 时间复杂度：O(Nlog⁡N)O(N \log N)O(NlogN)，主要来自排序操作
• 空间复杂度：O(N)O(N)O(N)，用于存储歌曲信息

代码实现

// Songs// UVa ID: 1346// Verdict: Accepted// Submission Date: 2025-11-19// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structSong{intid;intlength;doublefrequency;};boolcompare(constSong&a,constSong&b){return(a.frequency/a.length)>(b.frequency/b.length);}intmain(){intn;while(cin>>n){vector<Song>songs(n);for(inti=0;i<n;i++)cin>>songs[i].id>>songs[i].length>>songs[i].frequency;inttarget;cin>>target;sort(songs.begin(),songs.end(),compare);cout<<songs[target-1].id<<endl;}return0;}