题目链接:
--------------------------------------------------------------------------------------------------------
题目的特别之处在于只有 $+1$ $+5$ 这两种操作 我们要考虑如何利用这个条件
多想一下后可以发现 如果最优解的目标值为$x($将至少$k$个人的值增加到$x)$
那么一定存在一个人 他的初始值在 $[x - 4, x]$ 这个范围内
否则将$x$减去$5$后可以得到更优的解
因此可能成为最优解的目标值最多只有 $n * 5$ 种
现在考虑的便是在 $O(n)$ 枚举目标值的前提下 如何对于每个目标值快速计算出答案
我一开始的想法是根据 $mod 5$ 的余数分类 写$5$个数组记录下前缀和什么的
然而这样二分答案有一个 $log$ 二分数组下标又一个 $log$
尽管题目给了 $4s$ 应该可以过 但是总感觉这样做不够优雅
再次分析题目条件我们有可以发现 实际上每次询问都是与目标距离最小的 $k$ 个数 而这个$k$是不变的
于是现在问题就变成了维护一个数据结构 支持查找容器内最小的 $k$个数 以及添加一个数
这显然就是一个堆了 总的复杂度是 $O(n + nlogk)$
由于在 $mod 5$ 的$5$中情况下 所有初始值转移到目标值的代价多少的排序并不是一样的
因此我们维护$5$个堆就好
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N = 2e5 + 10; 8 const long long inf = 1e9; 9 int a[N], dis[N * 5];10 long long sum[5];11 long long ans = 1e18;12 int n, k, b, c, cnt;13 priority_queue q[5];14 int main()15 {16 scanf("%d%d%d%d", &n, &k, &b, &c);17 b = min(b, c * 5);18 for(int i = 1; i <= n; ++i)19 {20 scanf("%d", &a[i]);21 for(int j = 0; j < 5; ++j)22 dis[cnt++] = a[i] + j;23 }24 sort(a + 1, a + 1 + n);25 sort(dis, dis + cnt);26 cnt = unique(dis, dis + cnt) - dis;27 int now = 1;28 for(int i = 0; i < cnt; ++i)29 {30 int x = dis[i], kind =(inf + x) % 5;31 long long cost;32 while(now <= n && a[now] <= x)33 {34 for(int j = 0; j < 5; ++j)35 {36 cost = (inf + j - a[now]) / 5 * b + (inf + j - a[now]) % 5 * c;37 q[j].push(cost);38 sum[j] += cost;39 if((int)q[j].size() > k)40 {41 sum[j] -= q[j].top();42 q[j].pop();43 }44 }45 ++now;46 }47 long long y = (inf + kind - x) / 5 * b * k;48 if((int)q[kind].size() == k)49 ans = min(ans, sum[kind] - y);50 }51 printf("%lld\n", ans);52 return 0;53 }