建网站打开需要验证,国内永久免费云服务器9930,一天一元网站建设,联通套餐原题
题目描述
在大学期间#xff0c;经常需要租借教室。
大到院系举办活动#xff0c;小到学习小组自习讨论#xff0c;都需要向学校申请借教室。
教室的大小功能不同#xff0c;借教室人的身份不同#xff0c;借教室的手续也不一样。
面对海量租借教室的信息经常需要租借教室。
大到院系举办活动小到学习小组自习讨论都需要向学校申请借教室。
教室的大小功能不同借教室人的身份不同借教室的手续也不一样。
面对海量租借教室的信息我们自然希望编程解决这个问题。
我们需要处理接下来 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 开始的整数编号。
输出格式
如果所有订单均可满足则输出只有一行包含一个整数 00。
否则订单无法完全满足输出两行第一行输出一个负整数 −1−1第二行输出需要修改订单的申请人编号。
数据范围
1≤n,m≤106, 0≤ri,dj≤109, 1≤sj≤tj≤n
输入样例
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4输出样例
-1
2
思路
借教室的订单其实就是在每天需要教室数量的数组上进行一个区间的增减可以用差分数组快速得到区间的变化而又因为订单满足先来后到即如果要处理第k个订单必须保证从1到k-1号订单全部可以满足那么就可以知道存在一个分界线有最后一个能处理的订单x在它之后的所有订单都不能处理在它之前的所有订单都可以满足。那么就可以用二分去做。 差分数组 bi是di相对于di-1的差值通过差值我们也能计算出订单的需要教室数。如果有变化就会在差分数组最左端di最右1的位置-di这就得到了教室数。
比如b12b4-2默认d00那么d1相对d0多2d1到d3不变d4相对d3少2。
那么我们很容易得到结果d00,d1~d32,d40即在d1到d3这几天我们每天都需要2个教室 代码
#includeiostream
#includecstdio
#includealgorithm
#includecstringusing namespace std;typedef long long LL;const int N1e610;int n,m;
int w[N]; //第i天有wi个教室可供租借
int d[N],s[N],t[N];
LL b[N]; //差分数组bool check(int mid)
{memset(b,0,sizeof b); //每次检查差分数组置零防止上次操作影响//为什么这里不用计算差分数组初始值b[i]d[i]-d[i-1]? 注意我们计算的是从1到mid的差分数组mid每次都会变如果不置零会导致上一次的差分数组影响这次的计算//bi是di相对于di-1的差值通过差值我们也能计算出订单的需要教室数//如果有变化就会在差分数组最左端di最右1的位置-di这就得到了教室数//比如b12b4-2默认d00那么d1相对d0多2d1到d3不变d4相对d3少2//那么我们很容易得到结果d00,d1~d32,d40即在d1到d3这几天我们每天都需要2个教室for(int i1;imid;i) //从1号到mid号订单用差分数组记录每天租借教室数量di{//si,ti表示第i份订单租借开始、结束的天数b[s[i]]d[i];b[t[i]1]-d[i]; //差分数组b记录变化}LL s0; //for(int i1;in;i){sb[i]; //s相当于原数组差分数组相加就是第i天需要的教室数量//如果有一天需要的教室比能提供的多就不行if(sw[i]) return false;}return true;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,w[i]);}for(int i1;im;i){scanf(%d%d%d,d[i],s[i],t[i]);}//二分共有m份订单找到最后一个能处理的订单int l0,rm; //从0开始有可能一个订单都不能满足while(lr){int midlr1 1; //取中点这里1是模板需要if(check(mid)) lmid;else rmid-1;}if(rm) puts(0); //所有订单都可以满足else printf(-1\n%d\n,r1); //如果不能满足输出第一个不能满足的编号} 为什么这里的代码不需要初始化差分数组 for(int i1;imid;i){b[i]d[i]-d[i-1];}
因为题目中初始情况下每一天所需的教室数都为0所需的教室数量是根据后面的订单才发生变化的也就是说要计算教室数量就可以通过订单差分数组来计算这些得到的差值加起来就是某天所需要的教室数量。 为什么L要从0开始 int l0,rm; //从0开始有可能一个订单都不能满足while(lr){int midlr1 1; //取中点这里1是模板需要if(check(mid)) lmid;else rmid-1;}if(rm) puts(0); //所有订单都可以满足else printf(-1\n%d\n,r1); //如果不能满足输出第一个不能满足的编号
当n和m都为1且这一天都不能满足正确答案应该是-1 1
但若从1开始则不会进入while循环直接输出0
若从0开始则会将r变为0输出-1 01 差分
再看一道经典差分题也可以用上面的【差分数组是原数组相邻元素的差值】来解
题目描述
输入一个长度为 n 的整数序列。
接下来输入 m 个操作每个操作包含三个整数 l,r,c表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n和 m。
第二行包含 n个整数表示整数序列。
接下来 m行每行包含三个整数 lrc表示一个操作。
输出格式
共一行包含 n个整数表示最终序列。
数据范围
1≤n,m≤100000 1≤l≤r≤n −1000≤c≤1000 −1000≤整数序列中元素的值≤1000
输入样例
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1输出样例
3 4 5 3 4 2
原解法
#includeiostream
using namespace std;
int m,n;
typedef long long ll;
const int N1e510;
int a[N];
int diff[N]; int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i){cina[i];}for(int i1;in;i){diff[i]a[i]-a[i-1]; //差分初始化}while(m--){int c,l,r;cinlrc;diff[l]c;diff[r1]-c; //这里是自增自减记得,- }for(int i1;in;i){a[i]diff[i]a[i-1];} //记得最后还原成原数组这样才能作用到原数组上面for(int i1;in;i){couta[i] ;}return 0;
}
新解法
#includeiostream
#includecstring
using namespace std;
int m,n;
typedef long long ll;
const int N1e510;
int a[N];
int diff[N]; int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i){cina[i];}for(int i1;in;i){diff[i]a[i]-a[i-1]; //差分初始化因为这个本身就有给整数序列所以需要计算而借教室那道题本身所需教室为0是通过一个一个订单计算得到的所以不需要计算初始值}while(m--){int c,l,r;cinlrc;diff[l]c;diff[r1]-c; //这里是自增自减记得,- }int s0;for(int i1;in;i){//不同之处这次我们直接通过差值来计算sdiff[i];couts ;} return 0;
}
这道题和借教室的不同就在于差分初始化因为这个题目本身就有给整数序列即原来的a是有初始值的所以需要计算差分数组的初始值而借教室那道题本身所需教室为0是通过一个一个订单计算得到的所以不需要计算初始值
