poj3111

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

K Best

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

3 2
1 1
1 2
1 3

Sample Output

1 2

Source

Northeastern Europe 2005, Northern Subregion

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿k个物品使得vi-x*wi大于等于0，对于满足条件的方案要记录下来。当然这里要贪心地拿最高的k个。注意这里卡STL！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 13:17:22
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct point
{
	int v, w, id;	
	double y;
	bool operator < (const point &a) const
	{
		return y > a.y;
	}
};

int n, k;
point aa[maxn];

inline int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i].y = aa[i].v - x * aa[i].w;
	sort (aa + 1, aa + 1 + n);

	double ans = 0;
	for (int i = 1; i <= n && i <= k; i++)
		ans += aa[i].y;

	if (sgn (ans) >= 0) return true;
	else return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d%d", &aa[i].v, &aa[i].w);
			aa[i].id = i;
		}

		double low = 0, high = 3e6, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0;
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}
		
		for (int i = 1; i <= k; i++)
		{
			if (i == 1) printf ("%d", aa[i].id);
			else printf (" %d", aa[i].id);
		}
		puts ("");
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

/*************************************************

Author :supermaker

Created Time :2016/1/29 13:17:22

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct point

{

int v, w, id;

double y;

bool operator < (const point &a) const

{

return y > a.y;

}

};

int n, k;

point aa[maxn];

inline int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

for (int i = 1; i <= n; i++)

aa[i].y = aa[i].v - x * aa[i].w;

sort (aa + 1, aa + 1 + n);

double ans = 0;

for (int i = 1; i <= n && i <= k; i++)

ans += aa[i].y;

if (sgn (ans) >= 0) return true;

else return false;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &k) != EOF)

{

for (int i = 1; i <= n; i++)

{

scanf ("%d%d", &aa[i].v, &aa[i].w);

aa[i].id = i;

}

double low = 0, high = 3e6, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

for (int i = 1; i <= k; i++)

{

if (i == 1) printf ("%d", aa[i].id);

else printf (" %d", aa[i].id);

}

puts ("");

}

return 0;

}

poj2976

poj1556

超客的水墨烟雨

poj3111

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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