3951280_ac_1344ms_2572k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define esp 1e-8
#define N 100001

using namespace std;

struct node
{
	int v, w;
	double y;
	int i;

	bool operator < (const node t)	const
	{
		return y > t.y;
	}
}p[N];
int n, k;
double lasts, s;

int main()
{
	int i;
	double a, b;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &p[i].v, &p[i].w);
		p[i].i = i + 1;
	}
	a = 0;b = 0;
	lasts = -1;
	while (true)
	{
		a = b = 0;
		for (i = 0; i < k; i++)
		{
			a += p[i].v;
			b += p[i].w;
		}
		s = a / b;
		if (fabs(s - lasts) < esp)
		{
			break;
		}
		for (i = 0; i < n; i++)
		{
			p[i].y = p[i].v - s * p[i].w;
		}
		sort(p, p + n);
		lasts = s;
	}
	for (i = 0; i < k - 1; i++)
		printf("%d ", p[i].i);
	printf("%d\n", p[i].i);
	return 0;
}