UVa 1346 Songs （贪心好题）

UVa 1346 Songs （贪心好题）2014-07-07 csdn博客 synapse7http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4092 思路：直接看这个和式，记A（i）=f（i）Σl（j）（1<=j<=i），则sum=ΣA（i）（别被下标迷惑了，s（i）完全可以用i代替）。

设sum已经达到最小，

记sum1 = A（i）+A（i+1） = （f（i）+f（i+1））*（l（1）+...+l（i-1）） + f（i）*l（i） + f（i+1）*l（i） + f（i+1）*l（i+1）

交换f（i）和f（i+1），交换l（i）和l（i+1），得sum2= （f（i）+f（i+1））*（l（1）+...+l（i-1）） + f（i）*l（i） + f（i）*l（i+1） + f（i+1）*l（i+1）

因为sum最小，必有sum1<=sum2，故f（i+1）*l（i）<=f（i）*l（i+1）

（也可以这么理解，频率越大的，长度越短的，即f（i）/l（i）越大的，位置越靠前）

完整代码：

01./*0.032s*/02.03.#include<bits/stdc++.h>04.using namespace std;05.06.struct node07.{08.int id;09.double l, f;10.bool operator < （const node& a） const11.{12.return a.f * l < f * a.l;13.}14.} a[65540];15.16.int main（）17.{18.int n, i, s;19.while （~scanf（"%d", &n））20.{21.for （i = 1; i <= n; ++i）22.scanf（"%d%lf%lf", &a[i].id, &a[i].l, &a[i].f）;23.scanf（"%d", &s）;24.nth_element（a + 1, a + s, a + n + 1）;25.printf（"%d
", a[s].id）;26.}27.return 0;28.}