题目

在大学期间，经常需要租借教室。

大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。

教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借。

共有 m 份订单，每份订单用三个正整数描述，分别为 ，表示某租借者需要从第  天到第  天租借教室（包括第  天和第  天），每天需要租借  个教室。 

我们假定，租借者对教室的大小、地点没有要求。

即对于每份订单，我们只需要每天提供  个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。

如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。

这里的无法满足指从第  天到第  天中有至少一天剩余的教室数量不足  个。 

现在我们需要知道，是否会有订单无法完全满足。

如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 n,m，表示天数和订单的数量。 

第二行包含 n 个正整数，其中第 i 个数为 ，表示第 i 天可用于租借的教室数量。 

接下来有 m 行，每行包含三个正整数 ，表示租借的数量，租借开始、结束分别在第几天。 

每行相邻的两个数之间均用一个空格隔开。

天数与订单均用从 1 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 0。

否则（订单无法完全满足）输出两行，第一行输出一个负整数 −1，第二行输出第一个需要修改订单的申请人编号。

数据范围

1≤n,m≤10^6,
0≤ri,dj≤10^9,
1≤sj≤tj≤n

输入样例：

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

输出样例：

-1
2

 

思路

        针对每个订单选择某一段连续的天数，来选择教室的个数，可以考虑到用差分来求解。可以将时间复杂度从O(n) 降到 O(1)。 

        差分参考：差分——前缀和的逆运算（一维+二维）-CSDN博客 

         完成每一个订单，每天的可用的教室的数量都是在严格单调下降的，因此可以考虑使用二分，来确定是那个订单导致教室的数量不够用。时间复杂度从O(n^2) 降到 O(nlogn)

        二分参考：二分查找（算法实质+模板）-CSDN博客

        如何通过二分确定订单是否可被满足？通过  计算前  个，包含  在内的所有订单总共 n 天内每天需要的天数（使用差分来计算）  ，如果某天的需要的教室数量大于当天能够分配的教室数量，那么表明该订单不能被满足。再向前走，判断前面的订单能否被满足，；否则，，找后面的订单能否被满足。

代码（详细注释）

import java.io.*;

class Main{
    static int N = 1000010;
    static int n,m;
    static long[] r = new long[N]; // 每天的教室数量
    static int[] d = new int[N]; // 订单需要的教室数量
    static int[] s = new int[N]; // 订单起始日期
    static int[] t = new int[N]; // 订单终止日期
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        str = in.readLine().split(" ");
        for(int i=1;i<=n;i++){
            r[i] = Long.parseLong(str[i-1]);
        }

        for(int i=1;i<=m;i++){
            str = in.readLine().split(" ");
            d[i] = Integer.parseInt(str[0]);
            s[i] = Integer.parseInt(str[1]);
            t[i] = Integer.parseInt(str[2]);
        }
        // 通过二分，找出第一个不能完全满足订单要求的编号，
        int l = 0, r1 = m; // l需要从0开始，比如说m=1，就不能进行while
        while(l<r1){
            int mid = l+r1+1>>1;
            if(check(mid)) l = mid;
            else r1 = mid-1;
        }
        // 最后的r是满足订单的最后一个
        if(r1==m) System.out.println(0);
        else System.out.println("-1"+"\n"+(r1+1));
        
    }
    public static boolean check(int mid){ // 计算到mid个订单的时候，n天内每天所需的教室的总数，每次都要对前mid个进行总数的计算，b[i]即表示第i天要满足前mid个订单的总数
        long[] b = new long[N];
        
        for(int i=1;i<=mid;i++) // 对所有订单进行差分计算
            insert(b,s[i],t[i],d[i]);
            
        for(int i=1;i<=n;i++){ // 再求差分的前缀和，即每一天需要的教室数量
            b[i] += b[i-1];
            if(b[i]>r[i]) return false;  // 对每一天都需要判断
        }

        return true;
    }
    public static void insert(long[] b,int s,int t,int d){ // 不应该提前计算，会把mid后面的订单也算进去
        b[s] += d;
        b[t+1] -= d;
    }
}