当前位置：首页 > news >正文

模拟赛 c7-B rgb

news 2026/8/17 0:25:24

题目描述

共 \(2N\) 张展牌，每张展牌包含：

整数编号 \((a_i)\)
类别 \((c_i \in {R,G,B})\)

要求将所有展牌两两配对，每张恰好属于一对，总代价规则：

一对类别相同：代价为 0。
一对类别不同：代价为两编号绝对值差 \((|x-y|)\)

总代价 = 所有配对代价之和，求最小总代价。

输入格式

第一行整数\(N\)，共 \(2N\) 张展牌
接下来 \(2N\) 行，每行整数 \((a_i)\) + 字符 \((c_i)\)。

输出格式

输出一个整数，最小总代价。

样例输入 1

样例输出 1

样例解释

最优方案：两张 \(R\) 配对（0 代价），\(G\) 与 \(B\) 配对 (|13-22|=9)，总和 9。

样例输入 2

样例输出 2

样例解释

对于样例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;
}