题解：P13846 [CERC 2023] Ball Passing
FishToucherrr · · 题解
P13846 [CERC 2023] Ball Passing
注：这是一篇模拟退火题解。
题目大意
有
要求将男生两两配对，女生两两配对。以坐标形式给出每个学生的位置，则每对配对的学生之间会有一个欧几里得距离。
目标是最大化所有配对的距离之和。
思路
读题可知，我们只需要对于男生和女生，各自求出所有配对的距离之和的最大值即可。
那么我们先只考虑对于其中一种性别，如何最大化答案。
而对于两两配对这种问题，我们可以考虑对这种性别的学生进行重新排列，让奇数位的学生与他之后最近的偶数位的学生配对即可，即排列中的第
于是，我们只需要找到对这种性别的学生的一种排列，使得按上述方式配对后，所有配对的距离之和最大即可。
那么，在观察到数据范围
具体做法
-
先用
std::random_shuffle()把一开始给的排列打乱，防止被卡（）。 -
设定一个初始温度
T ，然后进入漫长的降温环节。 -
每次降温时：随机选取一种性别，在这种性别的学生中随机选择两个学生交换位置，然后求出换位置后得到的排列对应的新答案。这样子求答案是很好求的：从前往后两个两个取学生，然后将这两个学生的距离累加到新答案中即可。
-
比较新答案
newans 和旧答案ans ：-
如果新答案大于旧答案，则直接用新答案代替旧答案，且采用这个新的排列继续进行下一步的降温。
-
否则，以一定的概率采用新排列（注意这里不用新答案代替旧答案），根据算法特色，这个概率为：
\Large e^\frac{newans-ans}{T} 这样选取概率可以保证：随着
T 的降低，排列的变化逐渐趋于稳定；新答案比旧答案小太多时，不采用新的排列。
-
-
降温，重复执行步骤 2\~5 直到温度降低到一定程度为止。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 51;
string S;
int n,bc=1,gc=1;//bc为男生人数，gc为女生人数
double ans;
struct obj
{
double x,y;
}b[MAXN],g[MAXN];
//分两个数组，用结构体存学生的信息，方便操作排列顺序
double getd(obj u,obj v)
{
return sqrt((u.x-v.x)*(u.x-v.x) + (u.y-v.y)*(u.y-v.y));
}
//求两个学生之间的距离
int getr(int l,int r)
{
return rand()%(r-l+1)+l;
}
//获取[l,r]的随机整数
double getp()
{
return (double)rand()/RAND_MAX;
}
//获取一个[0,1]的随机浮点数，用于概率相关计算
double getans()
{
double res = 0;
for (int i=2;i<=bc;i+=2) res += getd(b[i-1],b[i]);
for (int i=2;i<=gc;i+=2) res += getd(g[i-1],g[i]);
return res;
}
//获取当前排列状况下的答案
int main()
{
srand(time(NULL));
cin >> n >> S;
for (int i=1;i<=n;i++)
{
if (S[i-1] == 'B')
{
cin >> b[bc].x >> b[bc].y;
bc ++;
} else if (S[i-1] == 'G')
{
cin >> g[gc].x >> g[gc].y;
gc ++;
}
}
bc--,gc--;
//把男生和女生的信息分别输入到两个数组里，并统计男生和女生各自的人数
//注意字符串下标是从0开始的www
if (bc > 0) random_shuffle(b+1,b+bc+1);
if (gc > 0) random_shuffle(g+1,g+gc+1);
//对应步骤1，重排数组，注意特判某个性别学生人数为0的情况，不然可能会RE
double T = 100.0;
//对应步骤2，设定初始温度
while (T >= 0.01) //在温度低于一定数值时跳出循环
{
int s = getr(0,1),swp1,swp2;
//s表示当前选取的性别，0是女生，1是男生；swp1和swp2表示随机选取的两个学生在数组中对应的下标
if (s && bc > 0)
{
swp1 = getr(1,bc),swp2 = getr(1,bc);
swap(b[swp1],b[swp2]);
} else if (gc > 0)
{
swp1 = getr(1,gc),swp2 = getr(1,gc);
swap(g[swp1],g[swp2]);
} else continue;
//交换学生在排列中的位置，得到新的排列
//同样注意特判某个性别学生人数为0的情况
double newans = getans();
//获取新答案
if (newans <= ans && getp() > exp((newans-ans)/T))
{
if (s) swap(b[swp1],b[swp2]);
else swap(g[swp1],g[swp2]);
//这里先判断了不采用新排列的情况，不采用新排列其实就是把原来交换位置的两个学生再换回来
}
else
{
ans = max(newans,ans);
//采用新排列，且如果新答案比旧答案更大则取新答案
}
T *= 0.99999;//降温
}
cout << fixed << setprecision(6) << ans << endl;
//输出答案，精确到小数点后6位
return 0;
}Tips：
退火万岁！