443      阿裏雲  技術社區[雲棲]

xdu 1203 - put on make up 二分答案

  寫了這麼多題，總想不起來二分答案這種神方法。附帶下sort的默認比較函數

sort 中的比較函 數

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double a[10005],b[10005],t[10005];
int n,k;
bool ok(double mid)
{
    int i;
    double ans=0;
    for(i=0;i<n;i++)
        t[i]=a[i]-mid*b[i];
    sort(t,t+n,greater<double>());
    for(i=0;i<k;i++) ans+=t[i];
    return ans>0;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        int i;
        double t;
        for(i=0;i<n;i++)
            scanf("%lf",&t),a[i]=log(t);
        for(i=0;i<n;i++)
            scanf("%lf",&t),b[i]=log(t);
        double l=1.0,r=3.0,mid;
        while(r-l>1e-8)
        {
            mid=(l+r)/2.0;
            if(ok(mid))l=mid;
            else r=mid;
        }
        printf("%.3f\n",l);
    }
}

最後更新：2017-04-03 16:48:37

  上一篇： 3.2 PCI設備的數據傳遞

  下一篇： 5.1 TLP的格式