首页 > 代码库 > bzoj4868
bzoj4868
http://www.lydsy.com/JudgeOnline/problem.php?id=4868
三分+贪心
我们可以知道这是一个单峰函数
当A>B那么我们每次调整一个的价钱是最佳的,所以全部用B,如果A<B,那么我们尽量用A,不行再用B
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010; int n, m; ll A, B, C; ll b[N], t[N]; ll check(ll T) { ll tot1 = 0, tot2 = 0, cost = 0; for(int i = 1; i <= m; ++i) if(b[i] > T) tot1 += b[i] - T; else tot2 += T - b[i]; for(int i = 1; i <= n; ++i) if(t[i] < T) cost += C * (T - t[i]); if(A > B) cost += tot1 * B; else cost += min(tot1, tot2) * A + (tot1 - min(tot1, tot2)) * B; return cost; } int main() { scanf("%lld%lld%lld", &A, &B, &C); scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]); for(int i = 1; i <= m; ++i) scanf("%lld", &b[i]); if(C >= 10000000000000000ll) { ll lim = 10000000000000000ll; for(int i = 1; i <= n; ++i) lim = min(lim, t[i]); printf("%lld\n", check(lim)); return 0; } ll l = 1, r = 100010; while(r - l > 2) { ll lm = (2 * l + r) / 3, rm = (2 * r + l) / 3; ll val1 = check(lm), val2 = check(rm); if(val1 > val2) l = lm; else r = rm; } printf("%lld\n", min(min(check((2 * l + r) / 3), check((2 * r + l) / 3)), min(check(l), check(r)))); return 0; }
bzoj4868
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。