Poj Solution 3111

http://poj.org/problem?id=3111

#include <stdio.h>
#include <algorithm>
using namespace std;

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;
}