C 最大比例

C 最大比例

思路

对于每一个

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll read()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

const int N = 1e5;

ll n, k;

struct node
{
	ll v, w, id;
	double key;
	void calc(double mid)
	{
		key = 1.0 * v - 1.0 * mid * w;
	}
	bool operator<(const node &cmp)const
	{
		return cmp.key < key;
	}
} s[N + 5];

bool check(double mid)
{
	for(ll i = 1; i <= n; i++)
	{
		s[i].calc(mid);
	}
	sort(s + 1, s + n + 1);
	double sum = 0;
	for(ll i = 1; i <= k; i++)
	{
		sum += s[i].key;
	}
	return sum >= 0;
}

int main()
{
	n = read(), k = read();
	for(ll i = 1; i <= n; i++)
	{
		s[i].v = read(), s[i].w = read(), s[i].id = i;
	}
	double l = 0.0000001, r = 1000000;
	for(ll i = 0; i <= 100; i++)
	{
		double mid = (l + r) / 2.0;
		if(check(mid))
		{
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	for(ll i = 1; i <= k; i++)
	{
		cout << s[i].id << " ";
	}
	cout << endl;
	return 0;
}