首页 > 代码库 > codeforces VK cup 2016-round 1 D.Bear and Contribution
codeforces VK cup 2016-round 1 D.Bear and Contribution
题意大概就是有n个数字，要使至少有k个相同，可以花费b使一个数+5，可以花费c使一个数+1，求最小花费。
要对齐的数肯定是在[v,v+4]之间，所以分别枚举模为0~4的情况就可以了。
排序一下，然后化绝对为相对
例如有 3 6 8 14这4个数，模4，
耗费分别为c+2b 3c+b c+b 0
可以-2b（移动到14时=2*5+4，倍率2）变成c 3c-b c-b -2b
就是说每次都取倍率然后减其花费压入优先队列，若元素数量大于k就弹出最大的那个就可以了
/*没时间自己写个就把其他人的题解搞来了。。。*/#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <map>#include <stack>#include <vector>#include <string>#include <queue>#include <cstdlib>#include <cmath>#include <algorithm>#include <ctime>using namespace std;typedef pair<int, int> pii;typedef long long ull;typedef long long ll;typedef vector<int> vi;#define xx first#define yy second#define rep(i, a, n) for (int i = a; i < n; i++)#define sa(n) scanf("%d", &(n))#define vep(c) for(decltype((c).begin()) it = (c).begin(); it != (c).end(); it++)const int mod = int(1e9) + 7, INF = 0x3fffffff, maxn = 1e5 + 12;//ll que[maxn * 4];int ct[maxn * 2];//小根堆仿函数class cmp{public: bool operator()(const ll a, const ll b) { return a > b; }};int main(void) {#ifdef LOCAL freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif int n, k, b, c; while (cin >> n >> k >> b >> c) { rep (i, 0, n) sa(ct[i]), ct[i] += 1e9; sort(ct, ct + n); ll ans = 1ll << 60; if (c * 5 <= b) { ll sum = 0; for (int i = 0; i < n; i++) { sum += ct[i]; if (i >= k - 1) { ans = min(ans, ((ll)ct[i] * k - sum) * c); sum -= ct[i - k + 1]; } } } else { rep (md, 0, 5) { ll sum = 0; //int head = 0, tail = 0; priority_queue<ll, vector<ll>, cmp> que; rep (i, 0, n) { ll cc = (md + 5 - ct[i] % 5 ) % 5; ll bb = (ct[i] + cc) / 5; //等效处理之后的值. ll cost = bb * b - cc * c; sum += cost; // while (head == tail || que[tail - 1] > cost) que[tail++] = cost; que.push(cost); if (i >= k - 1) { ans = min(ans, (bb * k * b - sum)); sum -= que.top(); que.pop(); } } } } cout << ans << endl; } return 0;}
听说还有一个o(n)的解法，待后面做
codeforces VK cup 2016-round 1 D.Bear and Contribution
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。