2020-2021:teams:manespace:codeforces_643_div.2_e
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_643_div.2_e [2020/05/22 11:06] quantumbolt 创建 |
2020-2021:teams:manespace:codeforces_643_div.2_e [2020/05/22 18:46] (当前版本) quantumbolt |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 有$n$个用$a$<sub>$i$</sub>个相同的砖垒成的柱子，有三种操作：$add$ 给一个柱子加一块砖，代价为$a$ ,$remove$ 给一个柱子减一块砖，代价为$r$，$move$ 将一个柱子的砖块移动到另一个柱子上，代价为$m$，问当$n$个柱子高度相同时的最少代价 | 有$n$个用$a$<sub>$i$</sub>个相同的砖垒成的柱子，有三种操作：$add$ 给一个柱子加一块砖，代价为$a$ ,$remove$ 给一个柱子减一块砖，代价为$r$，$move$ 将一个柱子的砖块移动到另一个柱子上，代价为$m$，问当$n$个柱子高度相同时的最少代价 | ||
| ====题解==== | ====题解==== | ||
| - | 现对输入的砖块高度进行排序，$m$取$a+r$和$m$的最小值以保证代价最少 ，最后用三分法得到结果。 | + | 现对输入的砖块高度进行排序，$m$取$a+r$和$m$的最小值以保证代价最少 ，然后用三分法得到结果。很神奇 ~~~ |
| ====代码==== | ====代码==== | ||
| + | |||
| + | <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | #define ll long lnog | ||
| + | using namespace std; | ||
| + | |||
| + | ll p[100010]; | ||
| + | ll n, a, r, m; | ||
| + | ll f(ll mid) { | ||
| + | ll ct1, ct2; | ||
| + | ct1 = ct2 = 0; | ||
| + | for (ll i = 1; i <= n; i++) | ||
| + | if (p[i] < mid) | ||
| + | ct1 += mid - p[i]; | ||
| + | else | ||
| + | ct2 += p[i] - mid; | ||
| + | ll ct3 = min(ct1, ct2); | ||
| + | ct1 -= ct3, ct2 -= ct3; | ||
| + | return ct1 * a + ct2 * r + ct3 * m; | ||
| + | } | ||
| + | int main() { | ||
| + | cin >> n >> a >> r >> m; | ||
| + | m = min(a + r, m); | ||
| + | for (ll i = 1; i <= n; i++) | ||
| + | cin >> p[i]; | ||
| + | sort(p + 1, p + 1 + n); | ||
| + | |||
| + | ll l = 0, r = 1000000000; | ||
| + | while (l < r) { | ||
| + | // ll mid = l + r >> 1; | ||
| + | // ll midr = mid + r >> 1; | ||
| + | ll mid = l + (r - l) / 3; | ||
| + | ll midr = l + (2 * r - 2 * l + 2) / 3; | ||
| + | if (f(mid) > f(midr)) | ||
| + | l = mid + 1; | ||
| + | else | ||
| + | r = midr - 1; | ||
| + | } | ||
| + | cout << f(l) << endl; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/manespace/codeforces_643_div.2_e.1590116773.txt.gz · 最后更改: 2020/05/22 11:06 由 quantumbolt
