POJ2976
一、二分

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=1100;
int n,k;
ll a[maxn],b[maxn];
double c[maxn];
const double eps=1e-6;

bool check(double mid)
{

    double sum=0.0;
    for(int i=1;i<=n;i++)
        c[i]=a[i]-mid*b[i];
    sort(c+1,c+1+n);
    for(int i=n;i>k;i--)
        sum+=c[i];
    //cout<<"sum: "<<sum<<endl;
    return sum>0;
}

int main(void)
{
    while(scanf("%d%d",&n,&k),n||k)
    {
        double l=0.0,r=0.0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            r+=a[i];
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
        }

        double mid;
        while(r-l>eps)
        {
            mid=(r+l)/2;
            if(check(mid)) l=mid;
            else r=mid;
            //cout<<"l: "<<l<<" r: "<<r<<endl;
            //getchar();
        }

        printf("%.0f\n",((l+r)/2)*100);
    }
    return 0;
}

二、Dinkelbach

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=1100;
int n,k;
ll a[maxn],b[maxn];
struct node
{
    double vi;
    int i;
}c[maxn];
bool cmp(const node&a,const node &b)
{
    return a.vi>b.vi;
}
const double eps=1e-6;
int main(void)
{
    while(scanf("%d%d",&n,&k),n||k)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
        }

        double l=0.0,ans=0.0;
        while(1)
        {
            ans=l;
            for(int i=1;i<=n;i++)
            {
                c[i].vi=a[i]-l*b[i];
                c[i].i=i;
            }
            sort(c+1,c+1+n,cmp);
            double sum=0.0;
            double p=0.0,q=0.0;
            for(int i=1;i<=n-k;i++)
            {
                p+=a[c[i].i];
                q+=b[c[i].i];
                sum+=c[i].vi;
            }
            l=p/q;
            if(abs(ans-l)<eps) break;

        }
        printf("%.0f\n",l*100);
    }
    return 0;
}