题目描述
小美为了拯救世界能源危机，她准备了 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#include #include #include #include #include #include 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;}