题目描述

二分+差分 java要使用快读 不然会超时 本解法就超时
同时一定left=0,如果说第一个订单就不满足 此时最后left=right=0,输出就为1

样例

import java.util.*;

public class Main {
    /*
      二分思想：先想好选那个版本的，决定找mid是否要向上取整
      对订单进行二分，我们是要让l=mid,尽可能找到最大能满足的订单，那么输出的时候加+1，就是第一个不满足的订单。
      所以我们的模板，要选mid=l+r+1>>1
    */

    /*
      差分思想：对于区间l到r,如果我们想要l到r都操作一个数的，只需要对区间l到r的差分数组的l位置和r+1位置进行操作一个数

      对于本题来说，l[i]就是订单开始时间，r[i]就是结束时间，那么对b[l[i]]和b[l[i]]操作d（也就是租借的数量）
      再对差分数组相加就可以得到当天租借的数量，判断是否超出当天可以租借的数量。
    */

    static final int N = 1000010;//最大可能出现的订单数和天数
    static int n, m;//天数和订单数量
    static int[] w = new int[N];//存储每天可以租借的数量
    static int[] l = new int[N];//存储该申请人租借开始在第几天。
    static int[] r = new int[N];//存储该申请人租借结束在第几天。
    static int[] d = new int[N];//存储该申请人租借的数量
    static long[] b = new long[N];//存储差分数组

    static boolean check(int mid) {
        Arrays.fill(b, 0);
        for (int i = 1; i <= mid; i++) {
            b[l[i]] += d[i];
            b[r[i]+1]-= d[i];
        }

        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            //如果超出每天可租借的数量，返回false
            if (b[i] > w[i]) return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 1; i <= n; i++)
            w[i] = scanner.nextInt();
        for (int i = 1; i <= m; i++) {
            d[i] = scanner.nextInt();
            l[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
        }

        int left = 0, right = m;//这里一定left=0 如果说第一个订单就不满足 此时right=0,输出就为1
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (check(mid)) left = mid;
            else right = mid - 1;
        }

        if (right == m) {//全部满足，就输出0
            System.out.println("0");
        } else {
            System.out.println("-1");
            System.out.print(right+1);//我们找到的恰好是最后一个满足的订单，所以不满足的订单就是右边一个位置，就加1
        }
    }
}