题解：P13518 [KOI 2025 #2] 镜子

Doraeman · 2025-08-01 10:41:00 · 题解

本题的关键在于：用所有 N 个镜子的位置和我的起始位置 s，表示出我的“最终位置”。

对称点计算

如果我在 a 位置，使用 b 位置的镜子，经过对称后我的位置在 2b-a（题目给出），此处给出证明过程：

若 a>b，根据距离计算方法，我与镜子的距离是 a-b，对称后我在镜子左侧，位置是 b-(a-b)=2b-a；
若 a<b，同理，我与镜子的距离是 b-a，对称后我在镜子右侧，位置是 b+(b-a)=2b-a；
若 a=b，对称后的位置也是 b=2b-b=2b-a。

最终位置计算

现在，我们要将 N 个镜子 A_{1\sim N} 的位置按照一定顺序进行排序（这个顺序待会再讲，便于理解）。

设我第 i 次对称之前的位置是 S_i，排序后第 i 个镜子的位置是 B_i。
那么对称后的位置就是 S_{i+1}=2B_i-S_i。

同时，又有 S_i=2B_{i-1}-S_{i-1}。
所以推出：

S_{i+1}=2B_i-(2B_{i-1}-S_{i-1})\\ \ \ \ \ \ =2B_i-2B_{i-1}+S_{i-1}

设第 k 次对称后位置是 f(k)，可以得到一个递推式：

f(k)=2B_k-f(k-1)

现在来到了最关键的一步：观察正负号。
可以发现，上式中 f(k-1) 前面是“-”，而 f(k) 前面是 “+”。
然而，在 f(k+1) 的表达式中，f(k-1) 前面又变成了 “-”，而 f(k) 前面变成了“+”。

根据“负负得正”，f(i) 的表达式中，如果某个数的系数是 1，那么它在 f(i+1) 中系数就是 -1，在 f(i+2) 中系数又是 1。

继续找规律可以发现这个结论：在 f(N) 的表达式中，2B_{1,3,5,\dots,2\lfloor\frac{N-1}{2}\rfloor+1} 前的符号是 “-”，而 2B_{2,4,6,\dots,2\lfloor\frac{N}{2}\rfloor} 前的符号是 “+”。

也就是说，对于所有的 B_{1\sim N}，也对于排序前的 A_{1\sim N}，一共有 \lfloor\frac{N+1}{2}\rfloor 个正号“+”以及 \lfloor\frac{N}{2}\rfloor 个负号“-”要添加在这些数的前面。

此外，初始位置 s 前的符号还要分类讨论：

若 N 是奇数，s 前符号是“-”（因为第 1 次 s 前符号就是“-”）；
若 N 是偶数，s 前符号是“+”。

位置最大值

现在题目要求最终位置 f(N) 的最大值。

为了让这个值最大，我们要尽可能让大的数前面使用 “+”，小的数前面使用“-”。
由此我们也得到了排序的原则：从大到小，前 \lfloor\frac{N+1}{2}\rfloor 个值前面用“+”，其余的值（共 \lfloor\frac{N}{2}\rfloor 个）用“-”。
不要忘记乘上它们每个镜子前的系数 2。

最后还要分情况讨论 s 前的系数是 1 还是 -1。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, s, a[N];
long long ans;
int main(){
    cin >> n >> s;
    for(int i=1; i<=n; i++)
        cin >> a[i];

    // 贪心 排序 
    sort(a + 1, a + n + 1, greater<int>());

    // 正负号 统计答案 
    for(int i=1; i<=(n+1)/2; i++)
        ans += a[i] * 2;
    for(int i=(n+1)/2+1; i<=n; i++)
        ans -= a[i] * 2;

    // 分情况讨论 
    if(n % 2 == 0) ans += s;
    else ans -= s;

    cout << ans;
}