noj 1054 dropping tests 二分法.txt

ACM资料大集合

#include <stdio.h> 
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 1002
#define MAX 1000000002
__int64 a[NMAX];
__int64 b[NMAX];

//NOJ 1054 丢掉的考试成绩
//二分法查找
/*
输入：
4 2
4 2 0 1
7 3 1 10

输出
60

思路：
假设去掉k个数后，则有
(max)((a1+a2+..+ai)/(b1+b2+..+bi)) >m (共有n-k个a,b)
即(a1+a2+..+ai)-(m*b1+m*b2+..+m*bi)>0)
即A=(a1-m*b1)+(a2-m*b2)+..+(ai-m*bi)>0
当A>0时，表示m的值还可以取更大些
当A<0时，表示m的值要取小些,否则矛盾
因此，用二分法解决
二分法一开始取的最小值为(a1+a2+..+an)/(b1+b2+..+bn),最大值为(max)(ai/bi);
*/
bool cmp(__int64 a,__int64 b)
{
    return a>b ;
}
int func(int num,int cishu) 
{ 
    double low,high,max,mid;
    int i;
    long double tt[NMAX],ss;
    __int64 sa,sb;
    sa=sb=max=0;
	//取二分法一开始的最值
    for(i=1;i<=num;i++)
    {
        sa+=a[i];
        sb+=b[i];
        if(((double)a[i])/((double)b[i])>max) max=((double)a[i])/((double)b[i]);
    }
    low=((double)sa)/((double)sb);
    high=max;
    mid=(low+high)/2;
    while(high-low>0.0000003)
    {	//无限逼近答案
        ss=0;
        for(i=1;i<=num;i++)
            tt[i]=(double)a[i]-mid*((double)b[i]);
        sort(tt+1,tt+num+1,cmp);
        for(i=1;i<=num-cishu;i++)
            ss+=tt[i];
		//调整提示中所指的m的值
        if(ss>0) low=mid;
        else if(ss<0) high=mid;
        mid=(low+high)/2;
    }
    return (int)(mid*100+0.5);
}

int main()
{
    int i,num,cishu;
    scanf("%d%d",&num,&cishu);
    while(!(num==0&&cishu==0))
    {
        for(i=1;i<=num;i++)
            scanf("%I64d",&a[i]);
        for(i=1;i<=num;i++)
            scanf("%I64d",&b[i]);
        cout<<func(num,cishu)<<endl;
        scanf("%d%d",&num,&cishu);
    }
    return 0;
}