题目描述

多路归并+二分

样例

import java.util.Scanner;

/*
  多路归并: 每个等差数列放在一个集合里面，每次去找最大的技能加点

  二分：是对技能加点二分，找到某个值，当选到这个值的时候，技能刚好加了M次，请注意这个值可能有多个，最后要减去。
*/
public class Main {

    static final int N = 100010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[N];
        int[] b = new int[N];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }

        int l = 0, r = 1000000;
        while (l < r) {
            //每次我们要找的mid 都是要尽量大的
            int mid = l + r + 1 >> 1;
            if (check(a, b, n, m, mid)) l = mid;
            else r = mid - 1;
        }

        long res = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] >= r) {
                //求一下a[i]到r的项数
                int c = (a[i] - r) / b[i] + 1;
                //求一下末项，公差是负的
                int end = a[i] - (c - 1) * b[i];
                //统计一下，加了几次(就是项数)
                cnt += c;
                //等差数列求和 可能爆int
                res += (long) (a[i] + end) * c / 2;
            }
        }

        //r(也就是x)的值可能有多个,多加的要减去
        System.out.println(res - (cnt - m) * r);
    }

    static boolean check(int[] a, int[] b, int n, int m, int mid) {
        //res也是有可能爆int的
        long res = 0;
        for (int i = 0; i < n; i++) {
            //大于mid才去求一下，大于mid的项数
            if (a[i] >= mid) {
                //项数累加
                res += (a[i] - mid) / b[i] + 1;
            }
        }
        //看一下项数的总合是否大于等于m
        return res >= m;
    }
}