题意
参考 鱼塘钓鱼
升级的过程一定是贪心的,每次都会优先选择当前可选的提高攻击力最多的技能,所以升级m次的本质是选择所有技能的提高攻击力最多的前m项。
40pts做法
考虑到每次都会选择当前最大的那一项,可使用堆来维护,把每组技能(等差数列)都放进堆里,依次弹出m次最大值,即为答案。
但是本题m过大,弹出m次一定会tle
100pts做法
显然不能通过逐个求前m个最大值,肯定会tle,故本题的时间复杂度应不含m或只含logm。发现第m次升级是前m次中最小的,即每次升级m次都会有个最小值,且由数据范围可知该最小值在0~$10^6$之内,反向考虑,可以求出最小值x使得技能中≥x等于m。
根据等差数列的性质,对于每组等差数列,都能求出共有c项 ≥ x,再对前c项求和,加在一起就是最后结果。
设每组的等差数列A首项为a,公差为-b,若 Ac = a-(c-1)*b >= x, 可得c = (a-x)/b+1,cnt = $\sum{c}$即大于等于x的技能个数,如果cnt等于m即正解。故可在0~$10^6$二分出x,但是cnt不一定严格等于m,因为末尾可能由多个x,最后应该使ans -= x(cnt-m)
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N],b[N];
int n, m;
LL ans;
bool check(int mid)
{
LL cnt = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= mid)
cnt += (a[i]-mid)/b[i]+1;//该组等差数列有这么多项大于等于mid
}
return cnt >= m;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d%d",&a[i],&b[i]);//注意公差是-b
int l = 0,r = 1e6;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
LL cnt = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= r)//r即为目标x
{
int c = (a[i]-r)/b[i]+1;
int end = a[i] - (c-1)*b[i];
ans += (LL) (a[i]+end)*c/2;//求和前c项
cnt += c;
}
}
cout << ans - (cnt-m)*r << endl;//去重
return 0;
}