codeforces 908F

大讨论题

考虑绿点在什么情况下都要连通，那么我们以绿点出发考虑问题

考虑到两个绿点之间的红点和蓝点：

1.如果两个都没有：直接连绿点

2.如果只有一种(比如蓝)：那么直接连接两个绿点，然后绿——蓝——蓝——……——蓝——绿，然后删掉最大的一段

3.如果两种都有：有两个连法：(一)直接连两个绿点，然后如(2)一样断掉一段

　　　　　　　　　　　　　　(二)两个绿点间通过蓝连一次，红连一次

　　　　　　　　两种连法取较小值

然后单独考虑两端：直接连上相连的绿点即可

最后考虑没有绿点的情况：直接分别连通红点和蓝点

 1 #include<bits/stdc++.h>
 2 #define maxn 300005
 3 using namespace std;
 4 int n;
 5 int pos[maxn],col[maxn];
 6 vector<int> R,B;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     bool hasG=0;
11     for(int i=1;i<=n;++i)
12     {
13         char op[2];
14         scanf("%d",&pos[i]);
15         scanf("%s",op);
16         if(op[0]=='G')col[i]=0,hasG=1;
17         if(op[0]=='R')col[i]=1;
18         if(op[0]=='B')col[i]=2;
19     }
20     if(!hasG)
21     {
22         for(int i=1;i<=n;++i)
23         {
24             if(col[i]==1)R.push_back(pos[i]);
25             else B.push_back(pos[i]);
26         }
27         int ans=0;
28         if(R.size())ans+=R[R.size()-1]-R[0];
29         if(B.size())ans+=B[B.size()-1]-B[0];
30         printf("%d
",ans);
31     }
32     else
33     {
34         int lastG=0,ans=0;
35         for(int i=1;i<=n;++i)
36         {
37             if(col[i]==1)R.push_back(pos[i]);
38             else if(col[i]==2)B.push_back(pos[i]);
39             else
40             {
41                 if(!lastG)
42                 {
43                     if(R.size())ans+=pos[i]-R[0];
44                     if(B.size())ans+=pos[i]-B[0];
45                     lastG=pos[i];
46                     R.clear();B.clear();
47                 }
48                 else
49                 {
50                     int len=3*(pos[i]-lastG);
51                     if(!R.size()&&!B.size())
52                     {
53                         len-=2*(pos[i]-lastG);
54                     }
55                     else if(!R.size())
56                     {
57                         len-=pos[i]-lastG;
58                         int mx=0;
59                         for(int i=1;i<B.size();++i)mx=max(mx,B[i]-B[i-1]);
60                         mx=max(mx,max(B[0]-lastG,pos[i]-B[B.size()-1]));
61                         len-=mx;
62                     }
63                     else if(!B.size())
64                     {
65                         len-=pos[i]-lastG;
66                         int mx=0;
67                         for(int i=1;i<R.size();++i)mx=max(mx,R[i]-R[i-1]);
68                         mx=max(mx,max(R[0]-lastG,pos[i]-R[R.size()-1]));
69                         len-=mx;
70                     }
71                     else
72                     {
73                         int mx=0;
74                         for(int i=1;i<B.size();++i)mx=max(mx,B[i]-B[i-1]);
75                         mx=max(mx,max(B[0]-lastG,pos[i]-B[B.size()-1]));
76                         len-=mx;
77                         mx=0;
78                         for(int i=1;i<R.size();++i)mx=max(mx,R[i]-R[i-1]);
79                         mx=max(mx,max(R[0]-lastG,pos[i]-R[R.size()-1]));
80                         len-=mx;
81                     }
82                     ans+=min(len,2*(pos[i]-lastG));
83                     R.clear();B.clear();
84                     lastG=pos[i];
85                 }
86             }
87         }
88         if(R.size())ans+=R[R.size()-1]-lastG;
89         if(B.size())ans+=B[B.size()-1]-lastG;
90         printf("%d
",ans);
91     }
92 }

View Code