Kベストpoj 3111（01スコア計画---二点検索）
1119 ワード
タイトル:http://poj.org/problem?id=3111
考え方：与えられたn個の二元グループ（v，w）は、sigma（v）／sigma（w）の値が最大になるように、k個を保持します。
コード:
考え方：与えられたn個の二元グループ（v，w）は、sigma（v）／sigma（w）の値が最大になるように、k個を保持します。
コード:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int Maxn=100001;
const double eps=1e-8;
struct node{
int w,v,index;
double r;
};
node sn[Maxn];
int n,k;
bool cmp(node x,node y){
return x.r>y.r;
}
bool can(double mid)
{
for(int i=0;i<n;i++)
{
sn[i].r=sn[i].v-mid*sn[i].w;
}
//sort(sn,sn+n,cmp);
partial_sort(sn,sn+k,sn+n,cmp);
double sum=0;
for(int i=0;i<k;i++)
{
sum+=sn[i].r;
}
return sum>=0;
}
int main()
{
while(cin>>n>>k)
{
int sum=0;
for(int i=0;i<n;i++){
scanf("%d %d",&sn[i].v,&sn[i].w);
sn[i].index=i+1;
sum+=sn[i].v;
}
double lb=0.0,ub=sum*1.0;
while(fabs(ub-lb)>eps)
{
double mid=(lb+ub)/2;
if(can(mid)) lb=mid;
else ub=mid;
}
for(int i=0;i<k-1;i++){
cout<<sn[i].index<<" ";
}
cout<<sn[k-1].index<<endl;
}
return 0;
}