给网站怎么做tag标签,从代码角度分析网站怎么做,招生就业网站开发详情,wordpress图片展示插件题目描述
在大学期间#xff0c;经常需要租借教室。大到院系举办活动#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表示租借的数量租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 11 开始的整数编号。
输出格式
如果所有订单均可满足则输出只有一行包含一个整数 00。否则订单无法完全满足
输出两行第一行输出一个负整数 −1−1第二行输出需要修改订单的申请人编号。
输入输出样例
输入
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4输出
-1
2
思路暴力只能拿一半的分数所以用二分枚举答案优化
#include iostream
#include cstring
using namespace std;
int n,m;
long long q[1000010];
long long d[1000010],s[1000010],t[1000010];
long long diff[1000010],need[1000010],rest[1000010];差分数组 第i天所需教室数 第i天有的教室数
bool check(int x){memset(diff,0,sizeof diff);for(int i1;ix;i){diff[s[i]]d[i];第i天开始diff[t[i]1]-d[i];第i天结束}for(int i1;in;i){need[i]need[i-1]diff[i];if(need[i]rest[i]) return false;}return true;
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i) cinrest[i];for(int i1;im;i) cind[i]s[i]t[i];int l1,rm;if(check(n)) cout0;else{while(l1r){int mid(lr)/2;if(check(mid)) lmid;else rmid;}if(!check(l)) cout-1endll;else cout-1endlr; }return 0;
}
