General Problem Solving Techniques [Beginner-1]~H

Description

John Doe is a famous DJ and, therefore, has the problem of optimizing the placement of songs on his tapes. For a given tape and for each song on that tape John knows the length of the song and the frequency of playing that song. His problem is to record the songs on the tape in an order that minimizes the expected access time. If the songs are recorded in the order S_(s1),..., S_s(n)<tex2html_verbatim_mark> on the tape then the function that must be minimized is

$displaystyle sum^{{n}}_{{i=1}}$ f_s(i) $displaystyle sum^{{s(i)}}_{{j=1}}$ l_s(j)

<tex2html_verbatim_mark>

where f_s(i)<tex2html_verbatim_mark> is the frequency of playing the i<tex2html_verbatim_mark> -th song and l<tex2html_verbatim_mark> is the length of the song. Can you help John?

Input

The program input is from a text file. Each data set in the file stands for a particular set of songs that must be recorded on a tape. A data set starts with the number N<tex2html_verbatim_mark> (fits a 16 bit integer) of songs. Follow N<tex2html_verbatim_mark> the song specifications, and in the end, a number representing the position of a song S<tex2html_verbatim_mark> on the optimized tape. A song specification consists of the song identifier (fits an integer), the length of the song (fits a 16 bit integer), and the frequency of playing the song (a floating-point number). The program prints the identifier of the song S<tex2html_verbatim_mark> .

White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

Output

For each set of data the program prints the result to the standard output from the beginning of a line.

Note: An input/output sample is in the table below. There is a single data set that contains 5 song specifications. The first song has the identifier 1, length 10 and playing frequency 45.5 etc. The result for the data set is the identifier of the 3rd song on the optimized tape. It is 2 for the given example.

Sample Input

5
1      10     45.5
2      5      20 
30     20     10 
400    50     35 
15     17     89.9
3

Sample Output

2
解题思路：给你一份歌单，其中包括歌曲号，歌曲时长还有歌曲被点播的频率。现要求你刻下这些歌到一张光碟里，不同的刻录顺序，光碟也就不同，要求的顺序是让上面给出的公式的值尽可能地小。简单来说是一个贪心的背包问题。不过要小心数组越界问题，我第一次提交时就出现了这个问题，因为我没有把数组开大，导致了这个问题，还有要注意的是输入数据时要给出一个截止条件，当输入不合格时应该停止运行，不然会超时。我后面提交就是因为这个问题导致超时的。
程序代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=100010;
class Complex
{
public:
int x;
double y;
}a[N];
bool cmp(class Complex a1,class Complex a2)
{
return a1.y>a2.y;
}

int main()
{
int t;
while(scanf("%d",&t)!=EOF)
{
int m,n,i,counta;
double h;
for(i=0;i<t;i++)
{
scanf("%d%d%lf",&m,&n,&h);
a[i].x=m;
a[i].y=h/n;
}
sort(a,a+t,cmp);
scanf("%d",&counta);
printf("%d ",a[counta-1].x);
}
return 0;
}