NOIP模拟:能源(二分答案)

时间：2023-11-14 23:18:56

题目描述

小美为了拯救世界能源危机，她准备了 n 台蓄电池。一开始每台蓄电池有 ai 个单位的能量。

现在她想把 n 台蓄电池调整到能量相同。对于每台蓄电池可以给另一台蓄电池传递能量。
但是会有能量损耗，每次给 x 个单位的能量只能接受到 $ x - \frac{100 - k}{100}$的能
量。k 是损耗参数。小美想知道每个蓄电池最多能同时到多少能量。

输入格式

　　从文件 energy.in 中读入数据。
　　第一行两个整数 n，k。
　　第二行 n 个数表示 $a_i$。

输出格式

　　输出到文件 energy.out 中。

　　一行保留 6 位小数表示答案。

样例输入

　　3 50
　　4 2 1

样例输出

　　2.000000

题目分析

　  看到求最值问题先想到二分答案。本题只需二分最后的答案 :

　　现将输入的数组a排序，设当前枚举的答案为ans:

　　$$ret1 =  \sum_{i}^{a_i <= ans} ans - a_i$$

　　$$ret2 = \sum_{i}^{a_i > ans} a_i - ans$$

　　最后看看是否满足$ret1 >= ret2 × \frac{100 - k}{100}$

　　如果是则 l = mid 否则 r = mid;

　　小数二分时可使用for()循环。

for(int i = ; i <= ; i++){

    double mid = (l + r) / ;

    if(check(mid)) l = mid;

    else r = mid;

}

CODE

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = ;

const int oo = 0x3f3f3f3f;

const double eps = 1e8;

int n, k;

double a[N];

double maxx = -oo;

double p;

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline bool check(double m){

    double ret = ;

    for(int i = ; i <= n; i++){

        if(a[i] > m) ret += (double)(a[i] - m) * ( - p);

        else ret -= (double)(m - a[i]);

    }

    return ret >= ;

}

inline void solve(){

    sort(a + , a + n + );

    double l = , r = maxx + ;

    for(int i = ; i <= ; i++){

        double mid = (l + r) / 2.0;

        if(check(mid)) l = mid;

        else r = mid;

    }

    printf("%.6f", l);

}

int main(){

    //freopen("h.in", "r", stdin);

    n = read();

    k = read();

    p = (double)k / ;

    for(int i = ; i <= n; i++)

        scanf("%lf", &a[i]), maxx = max(maxx, a[i]);

    solve();

    return ;

}

相关文章