Poj2976 Dropping tests
思路
0/1分数规划简单题，二分枚举答案L，则对当前的情况有$cfrac{sum{aitimes xi}}{sum{bitimes xi}}>=L$ ，其中xi为1或0，表示第i个得分取或不取，公式可以转化为$sum{(ai-Ltimes bi)times xi}>=0 $ 则对所有得分而言$ai-Ltimes bi$ 越大的得分会使结果有效，所以以此为比较条件进行排序，优先取这些得分。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<algorithm>
using namespace std;
const int N = 1e3+10;
const double eps=1e-8;
int n,k;
double lim;
struct {
int a,b;
}st[N];
bool cmp(node a,node b){
return (100.0*a.a-lim*a.b)<(100.0*b.a-lim*b.b);
}
bool judge(int id){
return 100.0*st[id].a-lim*st[id].b>-eps;
}
bool check(double x){
lim=x;
double up=0,dw=0;
sort(st,st+n,cmp);
for(int i=k;i<n;i++){
up+=100.0*st[i].a;
dw+=1.0*st[i].b;
}
if((up/dw)-x>-eps) return 1;
return 0;
}
int main()
{
while(scanf("%d%d",&n,&k)&&(n||k)){
for(int i=0;i<n;i++){
scanf("%d",&st[i].a);
}
for(int i=0;i<n;i++){
scanf("%d",&st[i].b);
}
double l=0.0,r=100.0;
double mid;
while(r-l>eps){
mid = (l+r)/2.0;
if(check(mid)){
l=mid;
}
else{
r=mid-eps;
}
}
printf("%dn",(int)(l+0.5));
}
}
|
近期评论