「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
转载请注明出处,谢谢!