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