题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

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

我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj, sj, tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

题目分析

最容易想到的想法，根据订单依次将每天需要的教室数量求出来，当某个订单需要的教室数量已经不能由可用的教室数量满足，该订单就是需要修改的方法。

于是有暴力解。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
    public static void main(String []args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String temp = bf.readLine();
        String []str=temp.split(" ");
        int n=Integer.parseInt(str[0]);
        int m=Integer.parseInt(str[1]);
        int []day=new int[n+2];
        temp=bf.readLine();
        str=temp.split(" ");
        for(int i=1;i<=n;i++)
        {
            day[i]=Integer.parseInt(str[i-1]);
        }
        int res=0;
        int []needroom=new int[n+1];
        int d[]=new int [m+1],s[]=new int [m+1],t[]=new int [m+1];
        for(int i=1;i<=m;i++)
        {
            temp=bf.readLine();
            str=temp.split(" ");
            d[i]=Integer.parseInt(str[0]);
            s[i]=Integer.parseInt(str[1]);
            t[i]=Integer.parseInt(str[2]);

            for(int j=s[i];j<=t[i];j++)
            {
                needroom[j]+=d[i];
                if(needroom[j]>day[j])
                {
                    res=i;
                    break;
                }
            }
            if(res!=0)
                break;
        }
        int left=1;
        int right=m;
        if(res==0)
            System.out.println(res);
        else {
            System.out.println(-1);
            System.out.println(res);
        }
    }
}

运行结果

暴力解超时，进一步分析问题，由于我们需要频繁的修改区间信息（订单中的l,r）,因此可以使用差分数组来保存（0，m）个订单的修改操作，然后还原原来的最后判断弄一下是否有订单小于0。

差分数组

简单描述一下差分数组

使用cha[i]=arr[i]-arr[i-1] 来记录arr[i] 和 arr[i-1] 的差，z之后当需要查找 arr[i] 需要从arr[0] 一路还原回来，这样做的好处是，当我们有任何的区间修改操作时，只需要在差分数组上 cha[left] 和 cha[right+1] 进行修改，而不需要遍历整个arr[left...right], 坏处是 需要查找某一个arr[i]时，需要一步步还原回来，所以

该方法适用于区间频繁修改，而且这个区间范围是比较大的，正如本题，m，s,t数值范围很大。

对于所有订单[1，m],如果订单[1，j]能够使得某一天的教室数量不够，那么[1,m]一定能够使得某一天的教室数量不够，找到第一个出现这种情况的 j（某天教室数量不够），使用二分查找。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
    //r[i] 表示第i天可用于租借的教室数量
    //d[i] 表示第i个订单租借的数量
    //s[i] 表示第i个订单的开始时间
    //t[i] 表示第i个订单的结束时间
    public static boolean check(int mid,int n,int m,int []r,int []d,int []s,int []t) {
        int[] cha = new int[n + 2];//差分数组
        int[] r1 = new int[n + 1];
        for (int i = 1; i <= n; i++)
            r1[i] = r[i];
        for (int i = 1; i <= mid; i++)
        {
            cha[s[i]]-=d[i];
            cha[t[i]+1]+=d[i];
        }
        for(int i=1;i<=n;i++)
        {
            cha[i]+=cha[i-1];
            r1[i]+=cha[i];
            if(r1[i]<0)
                return false;
        }
        return true;
    }


    public static void main(String []args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String temp = bf.readLine();
        String []str=temp.split(" ");
        int n=Integer.parseInt(str[0]);
        int m=Integer.parseInt(str[1]);
        int []day=new int[n+2];
        temp=bf.readLine();
        str=temp.split(" ");
        for(int i=1;i<=n;i++)
        {
            day[i]=Integer.parseInt(str[i-1]);
        }
        int res=0;
        int d[]=new int [m+1],s[]=new int [m+1],t[]=new int [m+1];
        for(int i=1;i<=m;i++)
        {
            temp=bf.readLine();
            str=temp.split(" ");
            d[i]=Integer.parseInt(str[0]);
            s[i]=Integer.parseInt(str[1]);
            t[i]=Integer.parseInt(str[2]);
        }
        int left=1;
        int right=m;
        while(left<=right)
        {
            int mid=(left+right)>>>1;
            if(check(mid,n,m,day,d,s,t))
                left=mid+1;
            else
                right=mid-1;

        }

        if(left-1==m)
            System.out.println(0);
        else {
            System.out.println(-1);
            System.out.println(left);
        }
    }
}