大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
【问题简述】
给定一个数n表示教室数
接下来n个数r[i]，表示每天可以借用的教室数量。
有m份订单，每份订单有三个数d[i],s[i],t[i]。表示从S[i]天到t[i]天，借用d[i]个教室。
现在询问能否满足所有订单。
如果能，则输出0
不能，则输出-1，换行输出最早不能满足的订单。
【输入样例】
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
【输出样例】
-1
2
【分析】
从数据范围看(n,m≤1,000,000)，算法的时间复杂度应在O(n)到O(nlogn)之间。可以用线段树维护，也可以用差分树状数组来维护。此处我们来使用一种神奇的算法。
大体思路是用二分答案二分时间，再用差分数组检验答案是否冲突。
二分答案不解释。。。
差分数组这块，懂得可以直接看代码。注意：差分本质是一种离线算法对于一个数列，我们用diff数组，表示后一个与前一个数的差值。例如:在[a,b]的区间中加上Δ(delta)，我们可以使diff[a]+=Δ，并使diff[b+1]-=Δ。
完成差分数组的计算后，从左向右再计算一次即可得到每天的总共订单数的确切值。判断是否有一天的预定教室数＞固有教室数
附上代码一份：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
struct node
{
int d,s,t;
}q[maxn];
int n,m;
int r[maxn];
int read()
{
int x=0;
char tmp;
tmp=getchar();
while(tmp<'0'||tmp>'9') tmp=getchar();
while(tmp>='0'&&tmp<='9')
{
x=(x<<1)+(x<<3)+tmp-'0';
tmp=getchar();
}
return x;
}
int diff[maxn];
bool check(int x)
{
memset(diff,0,sizeof(diff));
for(int i=1;i<=x;i++)
{
diff[q[i].s]+=q[i].d;
diff[q[i].t+1]-=q[i].d;
}
int tmp=0;
for(int i=1;i<=n;i++)
{
tmp+=diff[i];
if(tmp>r[i]) return 0;
}
return 1;
}
int main()
{
freopen("classroom.in","r",stdin);
freopen("classroom.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)
r[i]=read();
for(int i=1;i<=m;i++)
q[i].d=read(),q[i].s=read(),q[i].t=read();
int l=1,r=m,ans=0;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) l=mid+1;
else ans=mid,r=mid-1;
}
if(!ans) printf("0\n");
else printf("-1\n%d",ans);
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/172062.html原文链接：https://javaforall.net
