题解 - CodeForces 1130B Two Cakes
Published:
思路
一道贪心题！
因为两个人每次都必须走到下一个数字的位置，我们可以先把输入数据按照蛋糕的尺寸排序，将其坐标化。例如对于下面的输入（样例 3），
\[\large 4,1,3,2,2,3,1,4\]可以这样进行排序：
\[\large 1,1,2,2,3,3,4,4\]即可方便地按照顺序进行操作，当然要记录坐标（也就是第几个被输入的），所以最终记下的数组应该是这样的：
\[\large 2,7,4,5,3,6,1,8\] \[\large (1,1,2,2,3,3,4,4)\]那么就可以从左到右执行循环，每次循环，一个人在该数字的第一次出现的位置，一个人在第二次出现的位置，比如第一次循环，Dima 在位置 2，Sasha 在位置 7，然后比较两种走到下一个位置的方法，即
- Dima From 2 to 4 (2 steps)
Sasha From 7 to 5 (2 steps)
总共走了 \(2+2\) 步。 - Dima From 2 to 5 (3 steps)
Sasha From 7 to 4 (3 steps)
总共走了 \(3+3\) 步。
每次加上两种方案中较小的那一个。
具体实现
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
//定义结构体
struct shop{
int cur, data; //该商店的位置，售卖蛋糕的尺寸
}a[200010];
long long n, ans = 0;
//自定义比较函数，方便之后排序
bool cmp(shop a, shop b)
{
//在尺寸不同时把尺寸小的蛋糕放前面
if (a.data != b.data) return a.data < b.data;
//反之把位置靠前的放前面（这个其实可以省略不写，也不影响判断）
else return a.cur < b.cur;
}
int main()
{
cin >> n;
for (int i = 1; i <= n * 2; i++) {
cin >> a[i].data; //输入的是蛋糕的尺寸
a[i].cur = i; //记录蛋糕的位置
}
sort(a + 1, a + 1 + n * 2, cmp); //排序
//第一次两人的位置都在1，所以应该用尺寸为1的蛋糕位置分别-1相加
//化简即为a[1].cur + a[2].cur - 2
ans += a[1].cur + a[2].cur - 2;
for (int i = 2; i <= n; i++) {
//想要取得尺寸为i的蛋糕，必须从尺寸为i-1的蛋糕店出发
//根据输入，尺寸为i的蛋糕位置分别是2i-1和2i
int p = a[i * 2 - 1].cur, q = a[i * 2].cur;
//尺寸为i-1的蛋糕位置分别是2i-3和2i-2
int k = a[i * 2 - 3].cur, l = a[i * 2 - 2].cur;
//比较两种方案，取最小值
ans += min(abs(p - k) + abs(q - l), abs(p - l) + abs(q - k));
}
cout << ans << endl;
return 0;
}