题目描述
共 \(2N\) 张展牌，每张展牌包含：
- 整数编号 \((a_i)\)
- 类别 \((c_i \in {R,G,B})\)
要求将所有展牌两两配对，每张恰好属于一对，总代价规则：
- 一对类别相同：代价为 0。
- 一对类别不同：代价为两编号绝对值差 \((|x-y|)\)
总代价 = 所有配对代价之和，求最小总代价。
输入格式
- 第一行整数\(N\)，共 \(2N\) 张展牌
- 接下来 \(2N\) 行，每行整数 \((a_i)\) + 字符 \((c_i)\)。
输出格式
输出一个整数，最小总代价。
样例输入 1
2
10 R
20 R
13 G
22 B
样例输出 1
5
样例解释
最优方案：两张 \(R\) 配对（0 代价），\(G\) 与 \(B\) 配对 (|13-22|=9)，总和 9。
样例输入 2
3
1 R
100 R
2 G
101 G
50 B
60 B
样例输出 2
0
样例解释
对于样例1：
共4张展牌，需要配成2对。所有可能的主要配对⽅式如下：
-
把两张 \(R\) 类展牌配在⼀起，代价为0；再把 \(G\) 类展牌和 \(B\) 类展牌配在⼀起，代价为\(|13-22|=9\)，总代价为9。
-
把编号为10的 \(R\) 类展牌和编号为13的 \(G\) 类展牌配在⼀起，代价为3；把编号为20的 \(R\) 类展牌和编22为 的 \(B\) 类展 牌配在⼀起，代价为2，总代价为5。
-
把编号为10的 \(R\) 类展牌和编号为22的 \(B\) 类展牌配在⼀起，代价为12；把编号为20的 \(R\) 类展牌和编号为13的 \(G\) 类 展牌配在⼀起，代价为7，总代价为19。
因此最⼩总代价为5。
对于样例2：
\(R 、 G 、 B\) 三种类别的展牌数量都为偶数。蜗蜗可以把相同类别的展牌互相配对，所有配对的代价都是0，所以最⼩总代价为0。
数据范围
对于40%的数据，保证\(N≤80\)。
对于100%的数据，保证\(1≤N≤10^5,1≤a_i≤10^{15},c_i为R、G、B\)中的一个字符。
算法分析
因为展牌的数量为偶数，所以有两种可能：
- 三种展牌数量均为偶数，是最优的，代价为0。
- 有两种展牌的数量为奇数，剩下的为偶数
如果是第一种，则直接输出0，很简单。但如果是第二种情况，那么只需要考虑两种算法：
- 把两种为奇数的展牌各拿一个，拼凑在一起，可以用二分或双指针解决。
- 把为偶数的展牌拿两个，各和另外两种凑在一起，也可以用二分或双指针实现，不需要考虑重叠的状况，因为不影响答案。
现在我们就可以开始写代码了，用我上面的思路模拟即可。
我都是用二分写的，因为有内置函数lower_bound，功能是求出再给定的区间内第一个不小于key值的元素的地址。
AC代码
#include<bits/stdc++.h>
#define ll long long//不开long long见祖宗
using namespace std;
int n;
int cnt[5];
ll mn = 1e18;
ll a[5][200005];
void f(int x,int y){for(int i = 1; i<=cnt[x]; i++){int pos = lower_bound(a[y]+1,a[y]+1+cnt[y],a[x][i])-a[y];//找最接近的值//前两个是特判if(pos==1){mn = min(abs(a[y][pos]-a[x][i]),mn);}else if(pos==1+cnt[y]){mn = min(abs(a[y][pos-1]-a[x][i]),mn);}else{mn = min(min(abs(a[y][pos]-a[x][i]),abs(a[y][pos-1]-a[x][i])),mn);}}int z = 6-x-y;//算另一个偶数展牌的下标if(cnt[z]!=0){//存在另一个偶数的展牌ll mn1 = 1e18;for(int i = 1; i<=cnt[x]; i++){int pos = lower_bound(a[z]+1,a[z]+1+cnt[z],a[x][i])-a[z];//找最接近的值//前两个是特判if(pos==1){mn1 = min(abs(a[z][pos]-a[x][i]),mn1);}else if(pos==1+cnt[z]){mn1 = min(abs(a[z][pos-1]-a[x][i]),mn1);}else{mn1 = min(min(abs(a[z][pos]-a[x][i]),abs(a[z][pos-1]-a[x][i])),mn1);}}ll mn2 = 1e18;for(int i = 1; i<=cnt[y]; i++){int pos = lower_bound(a[z]+1,a[z]+1+cnt[z],a[y][i])-a[z];//和上面一样//也和上面一样if(pos==1){mn2 = min(abs(a[z][pos]-a[y][i]),mn2);}else if(pos==1+cnt[z]){mn2 = min(abs(a[z][pos-1]-a[y][i]),mn2);}else{mn2 = min(min(abs(a[z][pos]-a[y][i]),abs(a[z][pos-1]-a[y][i])),mn2);}}mn = min(mn1+mn2,mn);//取最小值}
}
int main(){cin>>n;n*=2;//千万不要忘记*2！！！for(int i = 1; i<=n; i++){ll x;char y;cin>>x>>y;//处理输入if(y=='R'){a[1][++cnt[1]] = x;}else if(y=='G'){a[2][++cnt[2]] = x;}else{a[3][++cnt[3]] = x;}}for(int i = 1; i<=3; i++){sort(a[i]+1,a[i]+1+cnt[i]);//排序}int x,y;if(cnt[1]%2==0 && cnt[2]%2==0 && cnt[3]%2==0){//最好的情况cout<<0;//直接输出return 0;}//找是哪两个奇数，求出下标if(cnt[1]%2==0 && cnt[2]%2==1 && cnt[3]%2==1){x = 2;y = 3;}else if(cnt[1]%2==1 && cnt[2]%2==0 && cnt[3]%2==1){x = 1;y = 3;}else{x = 1;y = 2;}f(x,y);//执行函数cout<<mn;//输出最小值return 0;
}
总结
这道题思路不是很好想，也不是很好证明，但只要思路想清了，代码就很好写了，直接二分加模拟即可，个人觉得可以评到黄。