划重点:
1.二分出第m个数是多少:设为x,则>=x的数那应该至少m个,当且仅当有多个x时个数>=m个。得到二分判断条件为 N组数据中>=x的个数,即累加每组数据中的个数>=m个
共N组数据。x是满足判断条件的最大的数,x再小时,肯定也满足条件,但肯定不是最大值,x再大时,肯定不满足条件,所以是红区间左端点
#include <iostream>
#include <cstring>
#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 ++ )//遍历n组数据
if (a[i] >= mid)
res += (a[i] - mid) / b[i] + 1;//项数=(末-首)/公差+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]);
//先找出第m项的数x
int l = 0, r = 1e6;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
//累加所有>=x的项
LL res = 0, cnt = 0;
for (int i = 0; i < n; i ++ )//遍历每一组
if (a[i] >= r)//只想取前m项,第m项是r,所以只取>=r的项
{
int c = (a[i] - r) / b[i] + 1;//项数
int end = a[i] - (c - 1) * b[i];
cnt += c;//记录总共去了多少项,可能超过m项
res += (LL)(a[i] + end) * c / 2;
}
printf("%lld\n", res - (cnt - m) * r);
return 0;
}