【POJ-3111】解题报告（二分，牛顿迭代，最大化平均值）

原始题目

K Best

  • Time Limit: 8000MS
  • Memory Limit: 65536K
  • Total Submissions: 13510
  • Accepted: 3466
  • 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 = {i1, i2, …, ik} 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^6, 1 ≤ w\_i ≤ 10^6\), both the sum of all \(v\_i\) and the sum of all \(w\_i\) do not exceed \(10^7\)).

Output

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

Sample Input

3 2
1 1
1 2
1 3

Sample Output

1 2

Source

Northeastern Europe 2005, Northern Subregion

题目大意

给定 \(n\) 个珍珠的价值和重量，要求取其中 \(k\) 个并使这 \(k\) 个珍珠的平均单位重量价值最大。

解题思路

  • 对平均单位重量价值二分（二分答案），每一次更新每个珍珠 \(r\_i=v\_i-k\*w\_i\) 即对平均单位重量价值的差值。
  • 排序后取差值最大的3个珍珠，若差值之和大于零（说明平均单位重量价值还不够大），left=mid，否则right=mid。逐渐逼近答案

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
const int maxn=1e5+5;


double l,r,mid;

int n,k;
struct jewl{
	int id;
	double vi,wi,ri;
	
}jewls[maxn];

bool cmp(jewl a,jewl b){
	return a.ri>b.ri;
}
int main(){
	while(~scanf("%d%d",&n,&k)){
		rep(i,1,n+1){
			scanf("%lf%lf",&jewls[i].vi,&jewls[i].wi);
			jewls[i].id=i;
		}
		l=0;r=INF;
		//开始二分寻找答案
		while(r-l>eps){
			mid=(l+r)/2;
			rep(i,1,n+1){
				jewls[i].ri=jewls[i].vi-mid*jewls[i].wi;
			}
			sort(jewls+1,jewls+n+1,cmp);
			//寻找最大的k个
			double sum=0;
			rep(i,1,k+1){
				sum+=jewls[i].ri; 
			}
			if(sum>=0) l=mid; 
			else r=mid;  
		} 
		rep(i,1,k+1){
			if(i==1) printf("%d",jewls[i].id);
			else printf(" %d",jewls[i].id); 
		}
		printf("\n");
	}
}

收获与反思

  • 浮点数二分
  • 最大化平均值经典题。