[NOIP2017模拟]能源

题目：

样例数据1

输入

3 50

4 2 1

输出

2.000000

样例数据2

输入

2 90

1 11

输出

1.909091

【数据规模】

对于100%的数据：

1<=n<=10000,0<=k<=99,0<= ai <=1000

分析：非常简单的题，直接二分答案就可以了，我考试时写得比较丑，用的是“夹逼”的思想去逼近正确答案，但是读入 ai 我tm写成%d了！GG，这次考试爆零。

代码：

1、自己改正后的

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;

int getint()
{
    int sum=,f=;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-;
        ch=getchar();
    }
    for(;ch>='0'&&ch<='9';ch=getchar())
        sum=(sum<<)+(sum<<)+ch-;
    return sum*f;
}

const double eps=;
int n,k,cnt1;
double tot,cnt,aver,paver,a[];

int main()
{
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);

    n=getint();k=getint();
    for(int i=;i<=n;++i)
    {
        scanf("%lf",&a[i]);//就是这里手贱了！！！
        tot+=a[i];
    }

    aver=tot/n;//算平均数 
    for(int i=;i<=n;++i)//先算一个aver和paver，之后进入“夹逼” 
        if(a[i]-aver>eps)
        {
            cnt+=a[i]-aver;
            a[i]=aver;
        }   

    paver=aver;
    aver=aver-cnt*k//n;
    while(paver-aver>eps)//很像二分的思想（但绝对比二分慢），让目前大于平均数的数全部降成平均数然后根据损耗算新的平均数，这样之前的平均数（paver）与现在的平均数（aver）差距就越来越小，直到小于精度就可以了 
    {   
        cnt=;
        for(int i=;i<=n;++i)
            if(a[i]-aver>eps)
            {
                cnt+=a[i]-aver;
                a[i]=aver;
            }

        paver=aver;
        aver=aver-cnt*k//n;
    }

    printf("%0.6f\n",aver);
    return ;
}
           

2、标代（真正的二分答案）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
const int Maxn=+;
const db eps=;

inline int read()
{
    char ch=getchar();int i=,f=;
    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
    while(isdigit(ch)){i=(i<<)+(i<<)+ch-'0';ch=getchar();}
    return i*f;
}

db n,k,a[Maxn],all;

inline bool check(db x)
{
    db res=;
    for(int i=;i<=n;i++)
    {
        if(a[i]>x)res+=(a[i]-x)*((db)-k);
        else res-=(x-a[i]);
    }
    return res>=;
}

int main()
{
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);
    n=read(),k=read();
    k/=;
    for(int i=;i<=n;i++)a[i]=read(),all+=a[i];
    all/=(db)n;
    db l=,r=all+;
    while(r-l>eps)
    {
        db mid=(l+r)/();
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.6f",l);
}
           

本体结。