【Luogu1083】借教室

发表于 更新于 分类于 评论数： 阅读次数：

Source and Judge

NOIP2012 提高组 D2T2
Luogu1083
Caioj1555

Problem

【Brief description】

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息，其中第i天学校有$ri$个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为$dj,sj,tj$，表示某租借者需要从第$sj$天到第$tj$天租借教室（包括第$sj$天和第$tj$天），每天需要租借$dj$个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供$dj$个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第$sj$天到第$tj$天中有至少一天剩余的教室数量不足$dj$个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

【Input】

第一行包含两个正整数n,m，表示天数和订单的数量。

第二行包含n个正整数，其中第i个数为$ri$，表示第i天可用于租借的教室数量。

接下来有m行，每行包含三个正整数$dj,sj,tj$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

【Output】

如果所有订单均可满足，则输出只有一行，包含一个整数 0。

否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。

【Limited conditions】

对于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。

【Sample input】

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

【Sample output】

-1
2

【Sample explanation】

第 1 份订单满足后，4 天剩余的教室数分别为 0，3，2，3。

第 2 份订单要求第 2 天到第 4 天每天提供 3 个教室，而第 3 天剩余的教室数为 2，因此无法满足。

分配停止，通知第 2 个申请人修改订单。

Record

2h

upd 2019.10.5

一个线性做法：见oi之路的【一类线性二分】

Analysis1

请先思考后再展开

先来个线段树

区间最小值和区间减小，打个lazy标记

然后网上说的70分，却拿到了95

Code1

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct Nod
{
	int l,r,mid;
	int lc,rc;
	int mi,lz;
}p[MAXN*2];
int a[MAXN];
//*******************实现*******************
int ln=0;
int build(int l,int r)
{
	int t=++ln;
	int mid=(l+r)>>1;
	if(l<r)
	{
		p[t]=(Nod){l,r,mid,build(l,mid),build(mid+1,r),0,0};
		p[t].mi=mymin(p[p[t].lc].mi,p[p[t].rc].mi);
	}
	else p[t]=(Nod){l,r,mid,-1,-1,a[l],0};
	return t;
}
void update(int x)
{
	int lc=p[x].lc,rc=p[x].rc;
	if(lc>0) p[lc].mi+=p[x].lz,p[lc].lz+=p[x].lz;
	if(rc>0) p[rc].mi+=p[x].lz,p[rc].lz+=p[x].lz;
	p[x].lz=0;
}
void change(int x,int l,int r,int c)
{
	if(p[x].l==l and p[x].r==r)
	{
		p[x].mi+=c;
		p[x].lz+=c;
		return;
	}
	if(p[x].lz!=0) update(x);
	
	int lc=p[x].lc,rc=p[x].rc;
	if(r<=p[x].mid) change(lc,l,r,c);
	else if(l>p[x].mid) change(rc,l,r,c);
	else change(lc,l,p[x].mid,c),change(rc,p[x].mid+1,r,c);
	p[x].mi=mymin(p[p[x].lc].mi,p[p[x].rc].mi);
}
int ask(int x,int l,int r)
{
	if(p[x].l==l and p[x].r==r) return p[x].mi;
	if(p[x].lz!=0) update(x);
	
	int lc=p[x].lc,rc=p[x].rc;
	if(r<=p[x].mid) return ask(lc,l,r);
	if(l>p[x].mid) return ask(rc,l,r);
	return mymin(ask(lc,l,p[x].mid),ask(rc,p[x].mid+1,r));
}
//*******************主函数*******************
int qread()
{
	int s=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while(c>='0' and c<='9') s=s*10+c-'0',c=getchar();
	return s;
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) a[i]=qread();
	build(1,n);
	for(int i=1;i<=m;i++)
	{
		int d=qread(),l=qread(),r=qread();
		if(ask(1,l,r)>=d) change(1,l,r,-d);
		else
		{
			printf("-1\n%d",i);
			return 0;
		}
	}
	printf("0");
}

Analysis2

请先思考后再展开

网上看到了针对区间修改的”永久标记“，于是试一发

然鹅并没有任何卵用

Code2

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct Nod
{
	int l,r,mid;
	int lc,rc;
	int mi,lz;
}p[MAXN*2];
int a[MAXN];
//*******************实现*******************
int ln=0;
int build(int l,int r)
{
	int t=++ln;
	int mid=(l+r)>>1;
	if(l<r)
	{
		p[t]=(Nod){l,r,mid,build(l,mid),build(mid+1,r),0,0};
		p[t].mi=mymin(p[p[t].lc].mi,p[p[t].rc].mi);
	}
	else p[t]=(Nod){l,r,mid,-1,-1,a[l],0};
	return t;
}
void change(int x,int l,int r,int c)
{
	if(p[x].l==l and p[x].r==r)
	{
		p[x].mi+=c;
		p[x].lz+=c;
		return;
	}
	
	if(r<=p[x].mid) change(p[x].lc,l,r,c);
	else if(l>p[x].mid) change(p[x].rc,l,r,c);
	else change(p[x].lc,l,p[x].mid,c),change(p[x].rc,p[x].mid+1,r,c);
	p[x].mi=mymin(p[p[x].lc].mi,p[p[x].rc].mi)+p[x].lz;
}
int ask(int x,int l,int r,int lz)//注意标记叠加
{
	if(p[x].l==l and p[x].r==r) return p[x].mi+lz;//debug
	
	if(r<=p[x].mid) return ask(p[x].lc,l,r,lz+p[x].lz);
	if(l>p[x].mid) return ask(p[x].rc,l,r,lz+p[x].lz);
	return mymin(ask(p[x].lc,l,p[x].mid,lz+p[x].lz),ask(p[x].rc,p[x].mid+1,r,lz+p[x].lz));
}
//*******************主函数*******************
int qread()
{
	int s=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while(c>='0' and c<='9') s=s*10+c-'0',c=getchar();
	return s;
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) a[i]=qread();
	build(1,n);
	for(int i=1;i<=m;i++)
	{
		int d=qread(),l=qread(),r=qread();//scanf("%d%d%d",&d,&l,&r);
		if(ask(1,l,r,0)>=d) change(1,l,r,-d);
		else
		{
			printf("-1\n%d",i);
			return 0;
		}
	}
	printf("0");
}

Analysis3

请先思考后再展开

现在的目的就是加速辣

区间修改$O(Klogn)$ （减法）

区间验证$O(Klogn)$ （找最小值）

总时间$O(m\times 2Klogn)$

其中K是由于区间修改而导致的复杂度上升，当然打标记已经尽量优化了，多大我也不知道

那如果引入差分呢？

区间修改$O(1)$

区间验证$O(n)$ （暴力验证）

那么这个差分乍一看是没有这么优秀的，看起来像个暴力，但是具体实现也有两种：

①一个个搞过去，总时间$O(m\times n)$

②二分验证，验证的时候要花一点时间在把前面订单搞定，总时间$O(logm\times (m+n))$

于是，采用②，时间才会真正达到$O(nlogn)$的复杂度

而区间修改的线段树则有点危险

这tm怎么想得到？？？

Code3

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
int n;
int a[MAXN],s[MAXN];
int d[MAXN],st[MAXN],ed[MAXN];
//*******************实现*******************
bool check(int mid)
{
	memset(s,0,sizeof(s));//需求量
	for(int i=1;i<=mid;i++) s[st[i]]+=d[i],s[ed[i]+1]-=d[i];
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=s[i];
		if(sum>a[i]) return 0;
	}
	return 1;
}
//*******************主函数*******************
int main()
{
	int m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&st[i],&ed[i]);
	
	int l=1,r=m,ans=-1;//最左的
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(!check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	if(ans<0) printf("0");
	else printf("-1\n%d",ans);
}
相关文章推荐

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/b9a5.html
转载请注明出处，谢谢！