3111.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 50 行

Source

Problem Id:3111  User Id:fzk 
Memory:1228K  Time:1139MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

struct node{
	int v, w, id;
}nd[100010];

double r;

bool cmp( node &a, node &b ) {
	return a.v-a.w*r > b.v-b.w*r;
}

int main( ){
	int n, k, i;
	double t, s1, s2;
	scanf( "%d%d", &n, &k );
	for( i=0; i<n; i++ ) {
		scanf( "%d %d", &nd[i].v, &nd[i].w );
		nd[i].id = i+1;
	}

	t = 0;
	r = 1.0;
	while( r != t ) {
		std::sort( nd, nd+n, cmp );
		s1 = s2 = 0;
		for( i=0; i<k; i++ )
			s1 += nd[i].v, s2 += nd[i].w;
		t = r;
		r = s1/s2;
	}

	for( i=0; i<k; i++ )
		printf( "%d ", nd[i].id );

	return 0;
}