[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);
}
           

本體結。