算法1

一开始只想到了差分，实在是想不出来怎么用二分+差分去做
只用差分，只能过9个测试点

package day;

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;

public class 借教室 {

    static int n,m;
    static int a[];
    static int b[];
    static int d[]=new int [(int) (1e6+10)];

    public  static  void add(int l,int r,int c) {
        b[l]+=c;
        b[r+1]-=c;
    }

    public static boolean check (int r) {
        for(int i=1;i<=r;i++){
            d[i]=d[i-1]+b[i];
            if(d[i]<0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");
         n=Integer.parseInt(p[0]);
         m=Integer.parseInt(p[1]);
         a=new int [n+1];
         b=new int [n+100];
         p=bufferedReader.readLine().split(" ");
         for(int i=1;i<=n;i++){
             a[i]=Integer.parseInt(p[i-1]);
             add(i, i,a[i]);
         }

         for(int i=1;i<=m;i++){
             p=bufferedReader.readLine().split(" ");
             int l=Integer.parseInt(p[1]);
             int r=Integer.parseInt(p[2]);
             int c=Integer.parseInt(p[0]);
             add(l, r, c*-1);

             if(check(r)==false){
                 System.out.println(-1);
                 System.out.println(i);
                 return;
             }
         }
         System.out.println(0);

    } 

}

算法2

二分+差分

其中二分的主要思想是数据是否具有二段性

参考文献

y总的讲解！绝

代码

package day;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 借教室2 {

    /**
     * @param args
     */
    static int n,m;
    static int a[];
    static long b[];
    static int num[];
    static int s[];
    static int d[];

    static long f[]=new  long [1000010];
    public  static  void add(int l,int r,int c) {
        b[l]+=c;
        b[r+1]-=c;
    }

    public static boolean check(int k) {

        for (int i = 1; i <= n; i ++ ) f[i] = b[i];

        for (int i = 1; i <= k; i ++ )
        {
            f[s[i]] -= num[i];
            f[d[i] + 1] += num[i];
        }

        long  res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            res += f[i];
            if (res < 0) return false;
        }

        return true;

    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");
         n=Integer.parseInt(p[0]);
         m=Integer.parseInt(p[1]);
         a=new int [n+1];
         b=new long  [n+100];
         p=bufferedReader.readLine().split(" ");
         for(int i=1;i<=n;i++){
             a[i]=Integer.parseInt(p[i-1]);
             add(i, i,a[i]);
         }

         num=new int [m+10];
         s=new int [m+10];
         d=new int [m+10];

         for(int i=1;i<=m;i++){
             p=bufferedReader.readLine().split(" ");
             num[i]=Integer.parseInt(p[0]);
             s[i]=Integer.parseInt(p[1]);
             d[i]=Integer.parseInt(p[2]);

         }
         int l=1;
         int r=m;
         while(l<r){
             int mid = l + r >> 1;
            if (check(mid)) l=mid+1;
            else r=mid;
         }

         if(check(l)){
             System.out.println(0);
         }else{
             System.out.println(-1);
             System.out.println(r);
         }



    }

}