VIjos——V 1782 借教室 | | 洛谷——P1083 借教室
https://vijos.org/p/1782||
https://www.luogu.org/problem/show?pid=1083
描述
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。我们需要处理接下来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,第二行输出需要修改订单的申请人编号。
样例1
样例输入1
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
样例输出1
-1
2
限制
每个测试点1s
提示
对于10%的数据,有1≤ n,m≤ 10;
对于30%的数据,有1≤ n,m≤1000;
对于70%的数据,有1≤ n,m≤ 10^5;
对于100%的数据,有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。
来源
Noip2012提高组复赛Day2T2
线段树 维护区间最小值,如果最小值不满足需要结束、、线段树区间操作
#include <algorithm>
#include <cstdio> using namespace std; const int N(+);
int n,m,i,num,sta,ove; struct Tree
{
int l,r,num,flag;
}tree[N<<]; inline void read(int &x)
{
x=;register char ch=getchar();
for(;ch<''||ch>'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar())
x=x*+ch-'';
} void Tree_build(int now,int l,int r)
{
tree[now].l=l; tree[now].r=r;
if(l==r)
{
read(tree[now].num);
return ;
}
int mid=tree[now].l+tree[now].r>>;
Tree_build(now<<,l,mid);
Tree_build(now<<|,mid+,r);
tree[now].num=min(tree[now<<].num,tree[now<<|].num);
} inline void Tree_down(int now)
{
tree[now<<].num-=tree[now].flag;
tree[now<<].flag+=tree[now].flag;
tree[now<<|].num-=tree[now].flag;
tree[now<<|].flag+=tree[now].flag;
tree[now].flag=;
}
void Tree_change(int now,int l,int r,int x)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
if(tree[now].num<x)
{
printf("-1\n%d",i);
exit();
}
tree[now].flag+=x;
tree[now].num-=x;
return ;
}
if(tree[now].flag) Tree_down(now);
int mid=tree[now].l+tree[now].r>>;
if(mid>=r) Tree_change(now<<,l,r,x);
else if(mid<l) Tree_change(now<<|,l,r,x);
else
{
Tree_change(now<<,l,mid,x);
Tree_change(now<<|,mid+,r,x);
}
tree[now].num=min(tree[now<<].num,tree[now<<|].num);
} int main()
{
read(n); read(m);
Tree_build(,,n);
for(i=;i<=m;i++)
{
read(num);read(sta);read(ove);
Tree_change(,sta,ove,num);
}
puts("");
return ;
}
正解:二分+差分
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int N(+);
int n,m,room[N],num[N],sta[N],ove[N]; int if_,ch;
void read(int &x)
{
if_=x=; ch=getchar();
for(;ch<''||ch>'';ch=getchar())
if(ch=='-') if_=;
for(;ch>=''&&ch<='';ch=getchar())
x=x*+ch-'';
if(if_) x=(~x)+;
} int s[N],ans;
bool jud(int day)
{
memset(s,,sizeof(s));
for(int i=;i<=day;i++)
{
s[sta[i]]+=num[i];
s[ove[i]+]-=num[i];
}
int sum=;
for(int i=;i<=n;i++)
{
sum+=s[i];
if(sum>room[i])
return false;
}
return true;
} void Dichotomy()
{
int l=,r=m;
for(;l<=r;)
{
int mid=l+r>>;
if(!jud(mid))
{
ans=mid;
r=mid-;
}
else l=mid+;
}
} int main()
{
read(n); read(m);
for(int i=;i<=n;i++) read(room[i]);
for(int i=;i<=m;i++)
read(num[i]),read(sta[i]),read(ove[i]);
Dichotomy();
if(ans) puts("-1");
printf("%d",ans);
return ;
}
正解
最新文章
- MySQL 数据库主从复制架构
- LinkedHashMap源码详解
- Office 2010/2007 简繁体转换按钮不见了?
- 1.Mybatis原理
- CentOS 编译安装 mysql
- 深入研究 Win32 结构化异常处理(作者博客有许多SEH的研究文章)
- LINUX总结第13篇:LINUX下动态库及版本号控制
- Web模板
- 高效搭建Storm全然分布式集群
- Codeforces Round #257 (Div. 1)A~C(DIV.2-C~E)题解
- tab切换实现方式2
- Nodejs mongodb 管理组件adminmongodb
- Putty(菩提)远程连接服务器教程听语音
- Express NodeJs Web框架 入门笔记
- Thread.join(), CountDownLatch、CyclicBarrier和 Semaphore区别,联系及应用
- Mac中安装git后,终端运行git出错,提示安装Xcode
- day 13 - 1 迭代器
- 安装使用阿里云的yum源
- 12:集合map、工具类
- php输出json的内容