AcWing 4656. 技能升级
原题链接
困难
作者:
改了吧
,
2023-01-10 11:56:42
,
所有人可见
,
阅读 106
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 1e5 + 10;
const int R = (1 << 20) + 10;
const int Base = N / 2;
const int M = 2 * N;
const int P = 998244353;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k;
const LL mod = 1e8 - 3;
int a[N];
int b[N];
bool check(int x)
{
LL res = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= x) // 只有大于等于x才能至少加一次
{
res += ((LL)a[i] - x) / b[i] + 1;
}
}
if (res >= k)
{
return true;
}
return false;
}
void solve()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &a[i], &b[i]);
}
int l = 0;
int r = 1e6 + 1;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (check(mid))
{
l = mid; // 第一个增加技能总数大于等于k的数
}
else
{
r = mid;
}
}
// cout << l << ' ' << r << endl;
LL ans = 0;
LL cnt = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= l)
{
LL t = ((LL)a[i] - l) / b[i] + 1;
LL tail = a[i] - ((t - 1) * b[i]);
cnt += t;
ans += t * (a[i] + tail) / 2;
}
// cout << ans << endl;
}
cout << ans - (cnt - k) * l; // 可能有多个相同的边界上的数,减去
}
int main()
{
int t;
t = 1;
// scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}