POJ 2976 Dropping tests:01分数规划【二分】

题目链接:http://poj.org/problem?id=2976

题意:

  共有n场考试,每场考试你得的分数为a[i],总分为b[i]。

  你可以任意去掉k场考试。

  问你最大的 100.0 * ( ∑ a[i] / ∑ b[i] )的值。(四舍五入)

题解:

  相当于从n场考试中选n-k场。

  二分:

    二分最大答案 ∑ a[i] / ∑ b[i] >= L

    即:∑ a[i] - ∑(b[i]*L) >= 0

  check函数:

    求数组val[i] = a[i] - b[i]*L

    将val排序。

    取最大的n-k个val[i],求和为sum。

    若sum >= 0则满足条件,lef = mid.

    否则rig = mid.

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 1005
#define INF 10000000
#define EPS 0.000001 using namespace std; int n,m;
double ans;
double a[MAX_N];
double b[MAX_N];
double val[MAX_N]; void read()
{
for(int i=;i<n;i++)
{
scanf("%lf",&a[i]);
}
for(int i=;i<n;i++)
{
scanf("%lf",&b[i]);
}
} bool is_legal(double x)
{
for(int i=;i<n;i++)
{
val[i]=a[i]-x*b[i];
}
sort(val,val+n);
double sum=;
for(int i=n-;i>=m;i--)
{
sum+=val[i];
}
return sum>=;
} void solve()
{
double lef=;
double rig=;
while(rig-lef>EPS)
{
double mid=(lef+rig)/2.0;
if(is_legal(mid)) lef=mid;
else rig=mid;
}
ans=lef;
} void print()
{
printf("%.0f\n",ans*100.0);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n== && m==) break;
read();
solve();
print();
}
}
上一篇:C# winform项目中ListView控件使用CheckBoxes属性实现单选功能


下一篇:08.音频系统:第003课_Linux音频驱动程序:第006节_DAPM的kcontrol注册过程