2024“钉耙编程”中国大学生算法设计超级联赛（3）1011抓拍 题解_2024“钉耙编程”中国大学生算法设计超级联赛(4)

抓拍题解

2024“钉耙编程”中国大学生算法设计超级联赛（3）

抓拍

*Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 119 Accepted Submission(s): 65
*
Problem Description

学校里有 n 名同学，初始时第 i 位同学从 (xi,yi) 出发，以每秒 1 米的速度散步。

同学们散步的方向有东南西北四种可能。假设有一位同学正在位于 (0,0)，则下一秒︰

- 如果向东走，到达 (1,0)
- 如果向西走，到达 (−1,0)
- 如果向南走，到达 (0,−1)
- 如果向北走，到达 (0,1)

假设散步过程会进行无限长的时间，同学们散步的方向不会改变，并且忽略碰撞的情况（允许某个时刻多人在同一个点，互不影响）。

现在你可以选择某个非负整数秒时刻抓拍照片。

一张照片可以用长方形 ((e,n),(w,s)) 表示，东北角为 (e,n)，西南角为 (w,s)。

只有抓拍的照片包含了所有同学时，我们才称这张照片是完美的。

请选择某个时刻抓拍一张完美的照片，使得照片的周长最小。

Input

第一行一个整数 n (1≤n≤2×105)，代表人数。

接下来 n 行，第 i 行包含两个整数 xi,yi (−109≤xi,yi≤109) 和一个字符 di ，由空格分隔，描述第 i 位同学。

di 是 ‘E’, ‘W’, ‘S’, ‘N’ 之一，分别代表第 i 位同学散步的方向是东、西、南、北。

Output

输出一行一个整数，代表最短的完美照片的周长。

Sample Input

5
0 2 E
0 6 S
2 0 N
2 6 S
4 4 W
1
2
3
4
5
6

Sample Output

8
1

不同于官方题解，博主采用贡献值的方法，以空间换时间达到$O(n)$的时间复杂度，调试较麻烦但时间复杂度似乎有所降低
首先最小矩形周长肯定为$2\ast (max(x)+max(y)-min(x)-min(y))$
我们关注每一条边，以西边为例，我们仅需关注最西边向东的点$We$，最西边向西的点$Ww$，最西边不做东西运动的点$wd$

我们依次计算每个边的三个参数，并计算初始周长

int Ee=-1E9-1,We=1E9+1,Ww=1E9+1,Ew=-1E9-1,Nn=-1E9-1,Sn=1E9+1,Ns=-1E9-1,Ss=1E9+1,wd=1E9+1,sd=1E9+1,ed=-1E9-1,nd=-1E9-1;
 int maxe=-1E9-1,maxw=1E9+1,maxn=-1E9-1,maxs=1E9+1;
 for(int i=0;i<n;i++)
 {
     cin>>x>>y>>d;
     maxe=max(x,maxe);
     maxn=max(y,maxn);
     maxs=min(y,maxs);
     maxw=min(x,maxw);
     if(d=='E')
     {
         Ee=max(x,Ee);
         We=min(x,We);
         nd=max(y,nd);
         sd=min(y,sd);
     }
     else if(d=='W')
     {
         Ww=min(Ww,x);
         Ew=max(Ew,x);
         nd=max(y,nd);
         sd=min(y,sd);
     }
     else if(d=='N')
     {
         Nn=max(y,Nn);
         Sn=min(y,Sn);
         ed=max(ed,x);
         wd=min(ed,y);
     }
     else
     {
         Ss=min(y,Ss);
         Ns=max(y,Ns);
         ed=max(ed,x);
         wd=min(wd,y);
     }
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

而在$We$向$Ww$和$wd$靠近的时候，对边长的贡献为每格**-1**，而在超过$wd$但未超过$Ww$的阶段，边长贡献为0，而超过$Ww$以后贡献为**+1此处有一个细节，就是当两个人面对面交错的时候可能会出现0贡献的情况因此开一个mo数组，当对向出现交错的情况补充1贡献**
每次对最小差值进行情况分析，当贡献$<=0$的时候退出计算

vector<int>ze(4),pl(4),mo(4,0);
    if(Ww>We)
    {
        pl[0]=(Ww-We)/2;
    }
    else pl[0]=-1;
    if(We<wd)
    {
        ze[0]=wd-We;
    }
    else ze[0]=-1;
    if(pl[0]>=0&&pl[0]<ze[0]&&(Ww-We)%2)mo[0]=1;

    if(Ew>Ee)
    {
        pl[1]=(Ew-Ee)/2;
    }
    else pl[1]=-1;
    if(Ew>ed)
    {
        ze[1]=Ew-ed;
    }
    else ze[1]=-1;
    if(pl[1]>=0&&pl[1]<ze[1]&&(Ew-Ee)%2)mo[1]=1;

    if(Ns>Nn)
    {
        pl[2]=(Ns-Nn)/2;
    }
    else pl[2]=-1;
    if(Ns>nd)
    {
        ze[2]=Ns-nd;
    }
    else ze[2]=-1;
    if(pl[2]>=0&&pl[2]<ze[2]&&(Ns-Nn)%2)mo[2]=1;

    if(Ss>Sn)
    {
        pl[3]=(Ss-Sn)/2;
    }
    else pl[3]=-1;
    if(sd>Sn)
    {
        ze[3]=sd-Sn;
    }
    else ze[3]=-1;
    if(pl[3]>=0&&pl[3]<ze[3]&&(sd-Sn)%2)mo[3]=1;
    int cnt=0;
    for(int i=0;i<4;i++)
    {
        if(pl[i]>0&&ze[i]>0)cnt++;
        else if(pl[i]<0&&ze[i]>0)cnt--;
        else if(pl[i]==0&&ze[i]>0)cnt+=mo[i];
    }
    while(cnt){
        cnt=0;
        int minn=1E9+1;
        for(int i=0;i<3;i++)
        {
            if(ze[i]>0)minn=min(minn,ze[i]);
            if(pl[i]>0)minn=min(minn,pl[i]);
        }
        for(int i=0;i<4;i++)
        {

            if(pl[i]>0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;

            }
            else if(pl[i]<0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;

            }
            else if(pl[i]==0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;
            }
        }
        for(int i=0;i<4;i++)
        {
            pl[i]-=minn;
            ze[i]-=minn;
            if(pl[i]>0&&ze[i]>0)cnt++;
            else if(pl[i]<0&&ze[i]>0)cnt--;
            else if(pl[i]==0&&ze[i]>0)cnt+=mo[i];
        }
    }
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

附AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    int x,y;
    char d;
    int Ee=-1E9-1,We=1E9+1,Ww=1E9+1,Ew=-1E9-1,Nn=-1E9-1,Sn=1E9+1,Ns=-1E9-1,Ss=1E9+1,wd=1E9+1,sd=1E9+1,ed=-1E9-1,nd=-1E9-1;
    int maxe=-1E9-1,maxw=1E9+1,maxn=-1E9-1,maxs=1E9+1;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y>>d;
        maxe=max(x,maxe);
        maxn=max(y,maxn);
        maxs=min(y,maxs);
        maxw=min(x,maxw);
        if(d=='E')
        {
            Ee=max(x,Ee);
            We=min(x,We);
            nd=max(y,nd);
            sd=min(y,sd);
        }
        else if(d=='W')
        {
            Ww=min(Ww,x);
            Ew=max(Ew,x);
            nd=max(y,nd);
            sd=min(y,sd);
        }
        else if(d=='N')
        {
            Nn=max(y,Nn);
            Sn=min(y,Sn);
            ed=max(ed,x);
            wd=min(ed,y);
        }
        else
        {
            Ss=min(y,Ss);
            Ns=max(y,Ns);
            ed=max(ed,x);
            wd=min(wd,y);
        }

    }
    ll lengthn=((ll)maxn-(ll)maxs);
    ll lengthe=(ll)maxe-(ll)maxw;
    vector<int>ze(4),pl(4),mo(4,0);
    if(Ww>We)
    {
        pl[0]=(Ww-We)/2;
    }
    else pl[0]=-1;
    if(We<wd)
    {
        ze[0]=wd-We;
    }
    else ze[0]=-1;
    if(pl[0]>=0&&pl[0]<ze[0]&&(Ww-We)%2)mo[0]=1;

    if(Ew>Ee)
    {
        pl[1]=(Ew-Ee)/2;
    }
    else pl[1]=-1;
    if(Ew>ed)
    {
        ze[1]=Ew-ed;
    }
    else ze[1]=-1;
    if(pl[1]>=0&&pl[1]<ze[1]&&(Ew-Ee)%2)mo[1]=1;

    if(Ns>Nn)
    {
        pl[2]=(Ns-Nn)/2;
    }
    else pl[2]=-1;
    if(Ns>nd)
    {
        ze[2]=Ns-nd;
    }
    else ze[2]=-1;
    if(pl[2]>=0&&pl[2]<ze[2]&&(Ns-Nn)%2)mo[2]=1;

    if(Ss>Sn)
    {
        pl[3]=(Ss-Sn)/2;
    }
    else pl[3]=-1;
    if(sd>Sn)
    {
        ze[3]=sd-Sn;
    }
    else ze[3]=-1;
    if(pl[3]>=0&&pl[3]<ze[3]&&(sd-Sn)%2)mo[3]=1;
    int cnt=0;
    for(int i=0;i<4;i++)
    {
        if(pl[i]>0&&ze[i]>0)cnt++;
        else if(pl[i]<0&&ze[i]>0)cnt--;
        else if(pl[i]==0&&ze[i]>0)cnt+=mo[i];
    }
    while(cnt){
        cnt=0;
        int minn=1E9+1;
        for(int i=0;i<3;i++)
        {
            if(ze[i]>0)minn=min(minn,ze[i]);
            if(pl[i]>0)minn=min(minn,pl[i]);
        }
        for(int i=0;i<4;i++)
        {

            if(pl[i]>0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;

            }
            else if(pl[i]<0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;

            }
            else if(pl[i]==0&&ze[i]>0)
            {
                if(i/2)lengthn-=minn;
                else lengthe-=minn;
            }
        }
        for(int i=0;i<4;i++)
        {
            pl[i]-=minn;
            ze[i]-=minn;
            if(pl[i]>0&&ze[i]>0)cnt++;
            else if(pl[i]<0&&ze[i]>0)cnt--;
            else if(pl[i]==0&&ze[i]>0)cnt+=mo[i];
        }
    }
    cout<<(ll)lengthe*2+(ll)lengthn*2;
    return 0;
}

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149