将得到的分数存在a[] 数组里,将原总分存在b[] 数组里。
要求的是100*(∑ai)/(∑bi) 的最大值,嗯。。。是去掉k对数据之后。
用二分,就需要确定一个mid , 假定 100*(∑ai)/(∑bi) = mid .等价于 100*∑ai = mid *∑bi 等价于 100*∑ai - mid *∑bi =0 将求和符合提前,得到 ∑100*ai - ∑mid *bi =0
合并一下 ∑(100*a - mid *bi)=0
这样,只要mid 满足这个式子,那么就是满足原式的,也就是说,mid是通过那个式子求出来的,这样,只要将每队,根据 100*a - mid *bi进行排序,然后去除最小的k个,后面的所有求和,和为零,那么mid即为所求。通过二分算法举出mid即可。
#include <iostream> #include <cstdio> #include <cstring> #include <cstring> #include <cmath> #include <algorithm> using namespace std; int N,k; double a[1005],b[1005];//接收输入 double c[1005];//算出来的…… double sum; bool solve()//判断去掉k个的时候,所达到的结果是否满足公式 { sum = 0.0; for(int i = k;i<N;++i) { sum += c[i]; } return sum>0.0; } int main() { scanf("%d%d",&N,&k); while(!(N==0&&k==0)) { for(int i = 0;i<N;++i) { scanf("%lf",&a[i]); } for(int i = 0;i<N;++i) { scanf("%lf",&b[i]); } int tt = 100; double l = 0; double r = 100; double mid; while(tt--)//循环一百遍啊一百遍…… { mid = (l+r)/2.0; for(int i = 0;i<N;++i) { c[i] = 100*a[i]-mid*b[i]; } sort(c,c+N); if(solve()) l = mid; else r = mid; } int res = l+0.5000001;//四舍五入的方案…… printf("%d\n",res); scanf("%d%d",&N,&k); } return 0; }