AcWing 4656. 技能升级
原题链接
困难
作者:
我是java同学
,
2023-01-10 12:40:54
,
所有人可见
,
阅读 148
思路
- 经典贪心,
多路归并
算法
- 先想正确性,再考虑优化
- 每一个技能初始后是一个等差数列
- 先把所有序列的每一个数都放到一个集合里,可以点m个技能,表示可以在集合里任选m个数,同时要求总和最大,显然是选最大的,所以要排序(从大到小),选前m个数
- 每个序列都是倒序的等差数列,所以每个序列的第一个数一定是大于等于序列里的任何一个数,因此最大值一定是在每个序列的第一个数中选。
- 选完第一个数,删掉这个数,再从每个序列当前的最大中选,可以保证每个序列的第一个数是最大的,以此类推,所以最优解是可以做到的。
优化
- 如果数据范围不大的话,可以用优先队列$mlog(n)$,钓鱼那题可以,但本题不行,m太大
- 从大到小排名是第m个数可以通过二分找出来(假设是x),就是≥x的数的个数,也就是≥m的数的个数,也就是≥x+1的数的个数要<m。$nlog(n)$
- 二分完后后要求出≥x的个数,假设数列首项是a,公差是-b。$o(1)$
- 求出大于等于x的数的总和,可能结果会多k个,用等差数列公式
-
同类题同模型
鱼塘钓鱼
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];
bool check(int mid)
{
LL res = 0;
for (int i = 0; i < n; i ++)
if (a[i] > mid)
res += (a[i] - mid) / b[i] + 1;
return res >= m;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%d%d", &a[i], &b[i]);
int l = 0, r = 1e6;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
LL res = 0, cnt = 0;
for (int i = 0; i < n; i ++)
if (a[i] >= r)
{
int c = (a[i] - r) / b[i] + 1;//大于等于m的个数
int end = a[i] - (c - 1) * b[i];//求末项
cnt += c;
res += (LL)(a[i] + end) * c / 2;//等差数列求和
}
printf("%lld\n", res - (cnt - m) * r); //(cnt - m)多出来的数
return 0;
}