https://vjudge.net/problem/POJ-2976
又是一波c++AC,g++WA的题。。
先推导公式：由题意得 Σa[i]/Σb[i]<=x，二分求最大x。化简为Σ(a[i]-x*b[i])<=0，按a[i]-x*b[i]降序排列，从中取前n-m个和满足该式的话，就说明x多半是偏大了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll a[], b[];
double c[];
ll n, m;
bool cmp(const double a, const double b)
{
return a>b;
}
int C(double x)
{
for(int i = ; i < n; i++){
c[i] = a[i]-x*b[i];
}
sort(c, c+n, cmp);//降序
double ans=;
for(int i = ; i < n-m; i++){
ans += c[i];
}
return ans<=;//
}
int main()
{
while(~scanf("%lld%lld", &n, &m)){
if(!n&&!m) break;
for(int i = ; i < n; i++){
scanf("%lld", &a[i]);
}
for(int i = ; i < n; i++){
scanf("%lld", &b[i]);
}
double lb = , ub = ;
for(int i = ; i < ; i++){
//while(ub-lb>1e-6){
double mid = (ub+lb)/;
if(C(mid)){
ub = mid;
}
else lb = mid;
//cout << mid << endl;
}
printf("%.0lf\n", (ub*));
}
return ;
}