贪心01背包_wand

The cities of Byteland and Berland are located on the axis 𝑂𝑥. In addition, on this axis there are also disputed cities, which belong to each of the countries in their opinion. Thus, on the line 𝑂𝑥 there are three types of cities:

the cities of Byteland,
the cities of Berland,
disputed cities.
Recently, the project BNET has been launched — a computer network of a new generation. Now the task of the both countries is to connect the cities so that the network of this country is connected.

The countries agreed to connect the pairs of cities with BNET cables in such a way that:

If you look at the only cities of Byteland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables,
If you look at the only cities of Berland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables.
Thus, it is necessary to choose a set of pairs of cities to connect by cables in such a way that both conditions are satisfied simultaneously. Cables allow bi-directional data transfer. Each cable connects exactly two distinct cities.

The cost of laying a cable from one city to another is equal to the distance between them. Find the minimum total cost of laying a set of cables so that two subsets of cities (Byteland and disputed cities, Berland and disputed cities) are connected.

Each city is a point on the line 𝑂𝑥. It is technically possible to connect the cities 𝑎 and 𝑏 with a cable so that the city 𝑐 (𝑎<𝑐<𝑏) is not connected to this cable, where 𝑎, 𝑏 and 𝑐 are simultaneously coordinates of the cities 𝑎, 𝑏 and 𝑐.

Input
The first line contains a single integer 𝑛 (2≤𝑛≤2⋅105) — the number of cities.

The following 𝑛 lines contains an integer 𝑥𝑖 and the letter 𝑐𝑖 (−109≤𝑥𝑖≤109) — the coordinate of the city and its type. If the city belongs to Byteland, 𝑐𝑖 equals to ‘B’. If the city belongs to Berland, 𝑐𝑖 equals to «R». If the city is disputed, 𝑐𝑖 equals to ‘P’.

All cities have distinct coordinates. Guaranteed, that the cities are given in the increasing order of their coordinates.

Output
Print the minimal total length of such set of cables, that if we delete all Berland cities (𝑐𝑖=‘R’), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables. Similarly, if we delete all Byteland cities (𝑐𝑖=‘B’), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables.

Examples
inputCopy
4
-5 R
0 P
3 P
7 B
outputCopy
12
inputCopy
5
10 R
14 B
16 B
21 R
32 R
outputCopy
24
Note
In the first example, you should connect the first city with the second, the second with the third, and the third with the fourth. The total length of the cables will be 5+3+4=12.

In the second example there are no disputed cities, so you need to connect all the neighboring cities of Byteland and all the neighboring cities of Berland. The cities of Berland have coordinates 10,21,32, so to connect them you need two cables of length 11 and 11. The cities of Byteland have coordinates 14 and 16, so to connect them you need one cable of length 2. Thus, the total length of all cables is 11+11+2=24.

从昨晚一直改到现在，A了，要哭出来了o(╥﹏╥)o

题意：
B,R,P三种类型城市，每个城市位置各不同。
要求在城市之间建边，长度为距离长度。使得删除所有B城市后，R、P相互连通；删除R城市后，B、P相互连通。
求建边的最小长度和。

思路：
首先从简单情况着手：
假设没有P城市的情况，那么结果就是B城市连接和加上R城市连接和。
假设没有R城市的情况，那么结果就是B城市与P城市连在一起的连接和。
假设没有B城市的情况，那么结果就是R城市与P城市连在一起的连接和。

于是可以想到，只要将B和P依次连接起来，再把R和P依次连接起来，结果一定是满足题意的，花费也就是 $MX(P,B)-MI(P,B)+MX(P,R)-MI(P,R)$。考虑从这里进行优化。

B之间的连接和R之间的连接一定是独立的，关键就是加入了P以后，怎么利用P之间连的边优化结果。

于是我们从P着手，用P将城市划分为 X X X P Y Y Y P Z Z Z P N N N…
X部分城市与第一个P相连，N部分城市与最后一个P相连，这个结果唯一，好考虑。

关键就是相邻P之间城市要怎么连接。

讨论之后发现只有两种排列方案，
方案1花费为P间距离乘以3减去R间最大间距和B间最大间距
方案2花费为P间距离乘以2
将方案1和方案2花费取min就是连接相邻两个P的最小花费了。

由此问题得到了解决。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; ll a[maxn]; int b[maxn]; vector<int>pos; int main() { 
    int n;scanf("%d",&n); ll MI1 = 2e9,MX1 = -2e9; ll MI2 = 2e9,MX2 = -2e9; for(int i = 1;i <= n;i++) { 
    char op[10]; scanf("%lld%s",&a[i],op); if(op[0] == 'B') { 
    b[i] = 1; MI1 = min(MI1,a[i]); MX1 = max(MX1,a[i]); } else if(op[0] == 'R') { 
    b[i] = 2; MI2 = min(MI2,a[i]); MX2 = max(MX2,a[i]); } else if(op[0] == 'P') { 
    pos.push_back(i); b[i] = 3; } } ll ans = 0; if(pos.size() == 0) { 
    if(MI1 != 2e9) ans += MX1 - MI1; if(MI2 != 2e9) ans += MX2 - MI2; printf("%lld\n",ans); return 0; } int flag1 = 0,flag2 = 0; for(int i = 1;i <= pos[0];i++) { 
    if(b[i] == 1 && !flag1) { 
    flag1 = 1; ans += a[pos[0]] - a[i]; } if(b[i] == 2 && !flag2) { 
    flag2 = 1; ans += a[pos[0]] - a[i]; } } flag1 = 0,flag2 = 0; for(int i = n;i >= pos[pos.size() - 1];i--) { 
    if(b[i] == 1 && !flag1) { 
    flag1 = 1; ans += a[i] - a[pos[pos.size() - 1]]; } if(b[i] == 2 && !flag2) { 
    flag2 = 1; ans += a[i] - a[pos[pos.size() - 1]]; } } for(int i = 1;i < pos.size();i++) { 
    ll pre1 = a[pos[i - 1]],pre2 = a[pos[i - 1]]; ll mx1 = 0,mx2 = 0; for(int j = pos[i - 1];j <= pos[i];j++) { 
    if(b[j] == 1) { 
    mx1 = max(mx1,a[j] - pre1); pre1 = a[j]; } if(b[j] == 2) { 
    mx2 = max(mx2,a[j] - pre2); pre2 = a[j]; } } mx1 = max(mx1,a[pos[i]] - pre1); mx2 = max(mx2,a[pos[i]] - pre2); ll num1 = 2 * a[pos[i]] - 2 * a[pos[i - 1]]; ll num2 = 1ll * 3 * (a[pos[i]] - a[pos[i - 1]]) - mx1 - mx2; ans += min(num1,num2); } printf("%lld\n",ans); return 0; }