首页 > 代码库 > NOIP模拟:能源(二分答案)

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

2024-10-23 01:59:39   202人阅读

题目描述

小美为了拯救世界能源危机，她准备了 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 = 1; i <= 30; i++){    double mid = (l + r) / 2;    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 = 10050;const int oo = 0x3f3f3f3f;const double eps = 1e8;int n, k;double a[N];double maxx = -oo;double p;inline int read(){    int i = 0, f = 1; char ch = getchar();    for(; (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘; ch = getchar());    if(ch == ‘-‘) f = -1, ch = getchar();    for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar())        i = (i << 3) + (i << 1) + (ch - ‘0‘);    return i * f;}inline bool check(double m){    double ret = 0;    for(int i = 1; i <= n; i++){        if(a[i] > m) ret += (double)(a[i] - m) * (1 - p);        else ret -= (double)(m - a[i]);    }    return ret >= 0;}inline void solve(){    sort(a + 1, a + n + 1);    double l = 0, r = maxx + 1;    for(int i = 1; i <= 60; 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 / 100;    for(int i = 1; i <= n; i++)        scanf("%lf", &a[i]), maxx = max(maxx, a[i]);    solve();    return 0;}

 

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


联系
我们