建设银行甘肃兰州分行网站,山东省服务外包网,厦门市住房和建设局网站,群晖wordpress外网无法仿问一、题目大意
你经过了n次测试#xff0c;第i次测试共有b[i]道题目#xff0c;其中答对了a[i]道题目#xff0c;对于1in我们从中去掉k个#xff0c;使得剩余的值中a[i]的和除以b[i]的和最大。
二、思路
我们对平均值进行二分#xff0c;判断每个平均值mid是否能…一、题目大意
你经过了n次测试第i次测试共有b[i]道题目其中答对了a[i]道题目对于1in我们从中去掉k个使得剩余的值中a[i]的和除以b[i]的和最大。
二、思路
我们对平均值进行二分判断每个平均值mid是否能够达到如果能够达到就放大达不到就缩小输出最后一个满足条件的平均值即可。
判断平均值可达性的过程需要看下这三个不等式
(a1a2a3a4)/(b1b2b3b4)mid
a1 a2 a3 a4 mid * b1 mid * b2 mid * b3 mid * b4
(a1 - mid * b1) (a2 - mid * b2) (a3 - mid * b3) (a4 - mid * b4) 0
那么不难看出我们对于每一个mid计算a[i]-b[i]*mid然后把计算的结果排个序找出最大的n-k个求和与0比较即可判断mid是否可行。
三、代码
#include iostream
#include algorithm
using namespace std;
double eps 0.0001;
int n, k, a[1007], b[1007];
double express[1007];
void input()
{for (int i 0; i n; i){scanf(%d, a[i]);}for (int i 0; i n; i){scanf(%d, b[i]);}
}
bool compare(const double a, const double b)
{return a b;
}
bool judge(double mid)
{for (int i 0; i n; i){// 最大化平均值//(a1a2a3a4)/(b1b2b3b4)mid// a1 a2 a3 a4 mid * b1 mid * b2 mid * b3 mid * b4//(a1 - mid * b1) (a2 - mid * b2) (a3 - mid * b3) (a4 - mid * b4) 0express[i] a[i] * 1.0;express[i] - (mid * 1.0 * b[i]);}sort(express, express n, compare);double sum 0.0;for (int i 0; i (n - k); i){sum express[i];}return sum 0.000;
}
void binarySearch()
{double left 0.00, right 1.0001;while (left eps right){double mid (left right) / 2;if (judge(mid)){left mid;}else{right mid;}}left * 100;printf(%.0f\n, left);
}
int main()
{while (~scanf(%d%d, n, k)){if (n 0 k 0){break;}input();binarySearch();}return 0;
}
