poj 3111 K Best 二分搜索最大化平均值-白红宇

poj 3111 K Best 二分搜索最大化平均值

阅读量：4112 次

发布时间：2019-05-25

本文共 2235 字，大约阅读时间需要 7 分钟。

K Best

Time Limit: 8000MS		Memory Limit: 65536K
Total Submissions: 7623		Accepted: 1970
Case Time Limit: 2000MS		Special Judge

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

poj 3111 K Best 二分搜索最大化平均值 - smilesundream - smilesundream的博客 .

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

3 21 11 21 3

Sample Output

1 2

Source

, Northern Subregion

错因分析：不能写成

sigma(v)/sigma(w)<=x

分析：挑战上143页，二分搜索，记sigma(v)/sigma(w)>=x,问题转换成了求x得最大值，二分搜索就行

#include
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long LL; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; int num[105]; struct Node{ int w,v,id; double temp; }node[100005]; bool cmp(Node a,Node b) { return a.temp>b.temp; } int n,k; int ok(double x) { double sum=0; for(int i=1;i<=n;i++) node[i].temp=node[i].v-node[i].w*x; sort(node+1,node+1+n,cmp); for(int i=1;i<=k;i++) sum+=node[i].temp; return sum>=0; } int main() { while(~scanf("%d %d",&n,&k)) { for(int i=1;i<=n;i++) { scanf("%d %d",&node[i].v,&node[i].w); node[i].id=i; } double l=0,mid,r=1e6; for(int i=1;i<=40;i++) //开成100次会超时，20次会wa，可能有poj服务器的问题 { mid=l+(r-l)/2; if(ok(mid)) l=mid; else r=mid; } for(int i=1;i<=k;i++) printf("%d ",node[i].id); printf("\n"); } return 0; }

转载地址：http://yvgsi.baihongyu.com/

你可能感兴趣的文章