C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1562 玻璃切割

Problem

现在有一块玻璃,是长方形的(w 毫米× h 毫米),现在要对他进行切割。

切割的方向有两种,横向和纵向。每一次切割之后就会有若干块玻璃被分成两块更小的玻璃。在切割之后玻璃不会被移动。

现在想知道每次切割之后面积最大的一块玻璃是多少。

Solution

倒着做。

做法1:

multiset,每次删除之后维护两端最大值。

做法2:

并查集维护。

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
#include<cstdio>
#include<cmath>
#include<string>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
int w,h,n;
multiset<int>msh;
multiset<int>msv;
typedef multiset<int>::iterator mtpoi;
struct E{
bool is_x;
int t;
}e[200020];
char s[10];
int cnt1,cnt2,a[200020],b[200020];
int x;
ll ans[200020];
int main(){
//printf("%f",log2(200000));
scanf("%d%d%d",&h,&w,&n);
for(int i=1;i<=n;i++){
scanf("%s%d",s,&x);
if(s[0]=='H'){
e[i].is_x=true;
a[++cnt1]=x;
msh.insert(x);
}
else{
e[i].is_x=false;
b[++cnt2]=x;
msv.insert(x);
//printf("%d\n",x);
}
e[i].t=x;
}
msh.insert(0);
msh.insert(w);
msv.insert(0);
msv.insert(h);
sort(a+1,a+1+cnt1);
sort(b+1,b+1+cnt2);
a[cnt1+1]=w;
b[cnt2+1]=h;
int mxh=0,mxv=0;
for(int i=1;i<=cnt1+1;i++){
mxh=max(mxh,a[i]-a[i-1]);
}
for(int i=1;i<=cnt2+1;i++){
mxv=max(mxv,b[i]-b[i-1]);
}
ans[1]=mxh;
ans[1]*=mxv;

for(int i=n;i>=2;i--){
if(e[i].is_x==true){
msh.erase(e[i].t);
mtpoi r=msh.upper_bound(e[i].t);
mtpoi l=r;
l--;
mxh=max(mxh,*r-*l);//puts("1");
}
else{
msv.erase(e[i].t);
//printf("del %d\n",e[i].t);
mtpoi r=msv.upper_bound(e[i].t);
mtpoi l=r;
l--;
mxv=max(mxv,*r-*l);
//printf("%d %d\n",*l,*r);
}
ans[n-i+2]=mxh;
ans[n-i+2]*=mxv;
}
for(int i=n;i>=1;i--){
printf("%lld\n",ans[i]);
}
return 0;
}

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
93

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
#define fo(d,s,t) for(int d=s;d<=t;d++)
#define fo0(d,s,t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int rd() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int w,h,n;
struct E{
int l,r;
};
E ww[200020],hh[200020];
int wx[200020],hx[200020];
char s1[20];
int s2,cnt1,cnt2;
struct S{
char x;
int t;
};
S cur[200020];
ll ans=0;
ll anss[200020];
int main(){
w=rd();h=rd();n=rd();
//getchar();
for(int i=1;i<=n;i++){
s1[0]=getchar();
s2=rd();
//getchar();
cur[i].x=s1[0];
cur[i].t=s2;
if(s1[0]=='H'){
hx[++cnt1]=s2;
}
else{
wx[++cnt2]=s2;
}
}
sort(hx+1,hx+1+cnt1);
sort(wx+1,wx+1+cnt2);
hx[cnt1+1]=h;
wx[cnt2+1]=w;
int mxh=0,mxw=0;
for(int i=1;i<=cnt1+1;i++){
if(i<=cnt1)hh[hx[i]].l=hx[i-1];
if(i<=cnt1)hh[hx[i]].r=hx[i+1];
mxh=max(mxh,hx[i]-hx[i-1]);

}
for(int i=1;i<=cnt2+1;i++){
if(i<=cnt2)ww[wx[i]].l=wx[i-1];
if(i<=cnt2)ww[wx[i]].r=wx[i+1];
mxw=max(mxw,wx[i]-wx[i-1]);//
}
for(int i=n;i>=1;i--){
ans=mxw;
ans*=mxh;
anss[i]=ans;
if(cur[i].x=='H'){
int tmp1,tmp2;
tmp1=hh[hh[cur[i].t].l].r=hh[cur[i].t].r;
tmp2=hh[hh[cur[i].t].r].l=hh[cur[i].t].l;
mxh=max(tmp1-tmp2,mxh);//printf("-%d\n",mxh);
}
else{
int tmp1,tmp2;
tmp1=ww[ww[cur[i].t].l].r=ww[cur[i].t].r;
tmp2=ww[ww[cur[i].t].r].l=ww[cur[i].t].l;
mxw=max(tmp1-tmp2,mxw);
}
}
for(int i=1;i<=n;i++){
printf("%lld\n",anss[i]);
}
return 0;
}

  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/23386/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!