题意
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来 n 天的借教室信息,其中第 i 天学校有 ri 个教室可供租借。共有 m 份订单,每份订单用三个正整数描述,分别为 dj, sj, tj,表示某租借者需要从第 sj 天到第 tj 天租借教室(包括第 sj 天和第 tj 天),每天需要租借 dj 个教室。
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供 dj 个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj个。
现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。
读入
第一行包含两个正整数 n, m,表示天数和订单的数量。
第二行包含 n 个正整数,其中第 i 个数为 ri,表示第i天可用于租借的教室数量。
接下来有 m 行,每行包含三个正整数 dj, sj, tj,表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
输出
如果所有订单均可满足,则输出只有一行,包含一个整数 0。
否则(订单无法完全满足)输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。
样例
读入
4 3 2 5 4 3 2 1 3 3 2 4 4 2 4
输出
-1 2
算法分析---二分,差分
N为10^6,暴力存数组并每次判断为N方,会炸。
可以选择存到一定规模再判断,所以可以选择用二分,从一半开始,有误就往回,无误向后。
存储使用差分,可以理解为反过来的前缀和
//用差分重新处理r数组 for (int i=n; i>0; i--) r[i]-=r[i-1]; /* 样例: |------------------------------- day: | 1 2 3 4 5 |------------------------------- r | 2 5 4 3 0 --> | 2 3 -1 -1 0 |------------------------------- 加入第五天是因为结束日可能为n,后一天既n+1 */
在每个订单的起始点(sj),减掉定教室的数量;然后在结束日的后一天(tj+1)加回来。
正常二分
int l=1, r1=m; while (l<r1){...} /* 样例: |------------------------------- day: | 1 2 3 4 5 |------------------------------- r | 2 5 4 3 0 --> | 2 3 -1 -1 0 mid=2: |------------------------------- j=1 |-2 0 0 2 0 //2 1 3 |------------------------------- | 0 3 -1 1 0 //把这“两点”加进r数组(注意:程序中应该额外copy一个) |------------------------------- | 0=0 | 0+3=3 | 0+3-1=2 | 0+3-1+1=3 //依次求和,出现负数既为有误(不要加day5的) |------------------------------- j=2 | 0 -3 0 0 3 //3 2 4 |------------------------------- | 0 0 -1 1 3 //把这“两点”加进r数组 |------------------------------- | 0=0 | 0+0=0 | 0+0-1=-1 //依次求和,出现负数既为有误 mid=1: |------------------------------- j=1 |-2 0 0 2 0 //2 1 3 |------------------------------- | 0 3 -1 1 0 //把这“两点”加进r数组 |------------------------------- | 0=0 | 0+3=3 | 0+3-1=2 | 0+3-1+1=3 //依次求和,本次无误,l=r=2退出循环 |------------------------------- out: | -1 //check(r)=false,输出 | 2 |------------------------------- */
程序框架
读入
//读入 scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) scanf("%d", &r[i]); for (int i=1; i<=m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
差分化r数组
//用差分重新处理r数组 for (int i=n; i>0; i--) r[i]-=r[i-1];
主体二分
//二分 int l=1, r1=m; while (l<r1){ int mid=(l+r1)/2; if(check(mid)) r1=mid;//之前的程序里用ans存答案,实际上并不需要,r1等于ans else l=mid+1; }
check函数
//check函数 bool check(int k){ //复制数组r-->b(r为前缀和形式) for (int i = 1;i<= n; i++) b[i] = r[i]; //处理(加入两点) for (int i = 1;i<= k; i++){ b[s[i]] -= d[i]; b[t[i] + 1] += d[i]; } //判断结果 int aa=0; for (int i = 1; i <= n; i++){ aa+=b[i]; if(aa<0) return true; } return false; }
判断并输出
//判断输出 if (check(r1)) printf("-1\n%d\n", ans); else printf("0");
ac程序
#include<bits/stdc++.h> using namespace std; const int N = 1100000; int n,m; int r[N],d[N],s[N],t[N],b[N]; //检查函数 bool check(int k){ //复制数组(r为前缀和形式) for (int i = 1;i<= n; i++) b[i] = r[i]; //处理(两点) for (int i = 1;i<= k; i++){ b[s[i]] -= d[i]; b[t[i] + 1] += d[i]; } //判断 int aa=0; for (int i = 1; i <= n; i++){ aa+=b[i]; if(aa<0) return true; } return false; } int main(){ freopen("cla.in","r",stdin); //读入 scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) scanf("%d", &r[i]); for (int i=1; i<=m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]); //用前缀和(但是是减法)重新处理r for (int i=n; i>0; i--) r[i]-=r[i-1]; //二分 int l=1, r1=m; while (l<r1){ int mid=(l+r1)/2; if(check(mid)) r1=mid; else l=mid+1; } //判断输出 if (check(r1)) printf("-1\n%d\n", r1); else printf("0"); return 0; }