POJ 2675 - Songs

http://poj.org/problem?id=2675

概要

\(N\) 種類の曲を並べる。 各曲には識別子と長さ \(l_i\)、頻度 \(f_i\) が設定されている。 このとき、\(\sum_{i=1} ^ n f_{s_i} \sum_{j=1} ^ {s_i} l_{s_j}\) を最小化するように \(s_1, \ldots, s_N\) と曲を並べたとき、\(S\) 番目の曲の識別子を答える。

制約

• \(1 \le N < 2 ^ {16}\)

解法

曲0, 1があったとき、0 1 と並べるほうが 1 0 と並べるよりもいいのは、 \(f_0 l_0 + f_1(l_0 + l_1) \le f_1 l_1 + f_0(l_0 + l_1)\)、 つまり \(f_1 l_0 \le f_0 l_1\) のときである。 よって、\(\frac{l_i}{f_i}\) が小さいほうから貪欲に並べたものが最適な並べ方である。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct song
 7 {
 8   int id, l;
 9   double f;
10   bool operator<(const song& s) const { return s.f*l < f*s.l; }
11 };
12 
13 int main()
14 {
15   for (int N; scanf("%d", &N) != EOF;) {
16     vector<song> v(N);
17     for (int i = 0; i < N; i++) {
18       scanf("%d %d %lf", &v[i].id, &v[i].l, &v[i].f);
19     }
20     int S;
21     scanf("%d", &S);
22     sort(v.begin(), v.end());
23     printf("%d\n", v[S-1].id);
24   }
25   return 0;
26 }