#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int n, k;

struct Jel
{
	int w, v, id;
	double y;
}jel[maxn];

bool cmp(Jel a, Jel b)
{
	return a.y > b.y;	
}

bool C(double r)
{
	for(int i = 0; i < n; i++)	
	{
		jel[i].y = jel[i].v - jel[i].w * r;
	}
	sort(jel, jel + n, cmp);
	
	double sum = 0;
	for(int i = 0; i < k; i++)			 
	{
		sum += jel[i].y;
	}
	
	return sum >= 0.0;
}

void solve()
{
	double l = 0.0, r = 1.0;
	double mid;
	while(r - 1e-6 > l)
	{
		mid = (l + r) / 2;
		if(C(mid))	l = mid;
		else r = mid;
	}
	
	for(int i = 0; i < k - 1; i++)			// 
	{
		printf("%d ", jel[i].id);
	}
	printf("%d\n", jel[k - 1].id);

}

int main()
{
	scanf("%d %d", &n, &k);
	
	for(int i = 0; i < n; i++)
	{
		scanf("%d %d", &jel[i].v, &jel[i].w);
		jel[i].id = i + 1;
	}
		
	solve();
	
	return 0;
	
}

• Re:哪位大佬帮看下我的代码哪里有问题。。。实在找不到了。。 (1053) wangpeiyi9979 2019-05-25 00:25:21