Warning: session_start(): open(/tmp/sess_5181bf4fb903daba01b7a03f5210190b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====Restorer Distance====
====题意====
有$n$个用$a$$i$个相同的砖垒成的柱子，有三种操作：$add$ 给一个柱子加一块砖，代价为$a$ ,$remove$ 给一个柱子减一块砖，代价为$r$，$move$ 将一个柱子的砖块移动到另一个柱子上，代价为$m$，问当$n$个柱子高度相同时的最少代价
====题解====
现对输入的砖块高度进行排序，$m$取$a+r$和$m$的最小值以保证代价最少 ，然后用三分法得到结果。很神奇 ~~~
====代码====
#include
#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;
}