POJ2976 Dropping tests (最大化平均值/二分)-白红宇

POJ2976 Dropping tests (最大化平均值/二分)

阅读量：179 次

发布时间：2019-02-28

本文共 769 字，大约阅读时间需要 2 分钟。

问题描述：

这里写图片描述

这个题目，典型的最大化平均值，依然是水题，但是因为一些细节，导致提交好几次都wa。

细节：

1.题目是drop k 个，所以最后转换一下思想（和牛过河搬石子是一样的），在n个里选n-k个，则相当于drop k 个。

2.题目要求the average should be rounded to the nearest integer，就因为这个，wa了几次没发现。

代码如下：

#include
   
    #include
    
     using namespace std;const int maxn = 1000+10;const int INF = 1000000000;int a[maxn],b[maxn];double y[maxn];int n,k;bool C(double d){    for(int i=0; i
     
      = 0;}void solve(){    double lb = 0, ub = INF;    for(int i=0; i<100; i++)    {        double mid = (lb + ub) / 2;        if(C(mid)) lb = mid;        else ub = mid;    }    double p = 100 * lb;    int q;    if((int)(p + 0.5) > (int)p)    q = (int)p + 1;//关键细节    else q = (int)p;    printf("%d\n",q);}int main(){    while(scanf("%d%d",&n, &k)==2 && n)    {        for(int i=0; i

你可能感兴趣的文章