poj 3111 K Best

Description

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

Input

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).

The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

Sample Input

Sample Output

1 2

最大化平均值：

直接二分平均值x求出最大的sigma(vi-x*wi) 然后判断是否大于等于0即可

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=100005;
 9 struct node{
10     int w,v,id;
11     double pst;
12 }a[N];
13 int n,k;
14 int gi(){
15     int str=0;char ch=getchar();
16     while(ch>'9' || ch<'0')ch=getchar();
17     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
18     return str;
19 }
20 bool comp(const node &pp,const node &qq){return pp.pst>qq.pst;}
21 bool check(double ff){
22     for(int i=1;i<=n;i++){
23         a[i].pst=a[i].v-a[i].w*ff;
24     }
25     sort(a+1,a+n+1,comp);
26     double sum=0;
27     for(int i=1;i<=k;i++)sum+=a[i].pst;
28     if(sum>=0)return true;
29     return false;
30 }
31 int main()
32 {
33     n=gi();k=gi();
34     for(int i=1;i<=n;i++)a[i].v=gi(),a[i].w=gi(),a[i].id=i;
35     double l=0,r=1e7,mid;double exp=1e-7;
36     while(l<=r-exp){
37         mid=(l+r)/2;
38         if(check(mid))l=mid+exp;
39         else r=mid-exp;
40     }
41     for(int i=1;i<=k;i++)printf("%d ",a[i].id);
42     return 0;
43 }