专栏文章

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

DDoraeman
P13518题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miol3dem
此快照首次捕获于
2025/12/02 20:58
3 个月前
此快照最后确认于
2025/12/02 20:58
3 个月前
查看原文
本题的关键在于：用所有 NN 个镜子的位置和我的起始位置 ss，表示出我的“最终位置”。

对称点计算

如果我在 aa 位置，使用 bb 位置的镜子，经过对称后我的位置在 2b−a2b-a（题目给出），此处给出证明过程：
  • 若 a>ba>b，根据距离计算方法，我与镜子的距离是 a−ba-b，对称后我在镜子左侧，位置是 b−(a−b)=2b−ab-(a-b)=2b-a；
  • 若 a<ba<b，同理，我与镜子的距离是 b−ab-a，对称后我在镜子右侧，位置是 b+(b−a)=2b−ab+(b-a)=2b-a；
  • 若 a=ba=b，对称后的位置也是 b=2b−b=2b−ab=2b-b=2b-a。

最终位置计算

现在，我们要将 NN 个镜子 A1∼NA_{1\sim N} 的位置按照一定顺序进行排序（这个顺序待会再讲，便于理解）。
设我第 ii 次对称之前的位置是 SiS_i，排序后第 ii 个镜子的位置是 BiB_i。
那么对称后的位置就是 Si+1=2Bi−SiS_{i+1}=2B_i-S_i。
同时，又有 Si=2Bi−1−Si−1S_i=2B_{i-1}-S_{i-1}。
所以推出：
Si+1=2Bi−(2Bi−1−Si−1)     =2Bi−2Bi−1+Si−1S_{i+1}=2B_i-(2B_{i-1}-S_{i-1})\\ \ \ \ \ \ =2B_i-2B_{i-1}+S_{i-1}
设第 kk 次对称后位置是 f(k)f(k)，可以得到一个递推式：
f(k)=2Bk−f(k−1)f(k)=2B_k-f(k-1)
现在来到了最关键的一步：观察正负号。
可以发现，上式中 f(k−1)f(k-1) 前面是“−-”，而 f(k)f(k) 前面是 “++”。
然而，在 f(k+1)f(k+1) 的表达式中，f(k−1)f(k-1) 前面又变成了 “−-”，而 f(k)f(k) 前面变成了“++”。
根据“负负得正”，f(i)f(i) 的表达式中，如果某个数的系数是 11，那么它在 f(i+1)f(i+1) 中系数就是 −1-1，在 f(i+2)f(i+2) 中系数又是 11。
继续找规律可以发现这个结论：在 f(N)f(N) 的表达式中，2B1,3,5,…,2⌊N−12⌋+12B_{1,3,5,\dots,2\lfloor\frac{N-1}{2}\rfloor+1} 前的符号是 “−-”，而 2B2,4,6,…,2⌊N2⌋2B_{2,4,6,\dots,2\lfloor\frac{N}{2}\rfloor} 前的符号是 “++”。
也就是说，对于所有的 B1∼NB_{1\sim N}，也对于排序前的 A1∼NA_{1\sim N}，一共有 ⌊N+12⌋\lfloor\frac{N+1}{2}\rfloor 个正号“++”以及 ⌊N2⌋\lfloor\frac{N}{2}\rfloor 个负号“−-”要添加在这些数的前面。
此外，初始位置 ss 前的符号还要分类讨论：
  • 若 NN 是奇数，ss 前符号是“−-”（因为第 11 次 ss 前符号就是“−-”）；
  • 若 NN 是偶数，ss 前符号是“++”。

位置最大值

现在题目要求最终位置 f(N)f(N) 的最大值。
为了让这个值最大，我们要尽可能让大的数前面使用 “++”，小的数前面使用“−-”。
由此我们也得到了排序的原则：从大到小，前 ⌊N+12⌋\lfloor\frac{N+1}{2}\rfloor 个值前面用“++”，其余的值（共 ⌊N2⌋\lfloor\frac{N}{2}\rfloor 个）用“−-”。
不要忘记乘上它们每个镜子前的系数 22。
最后还要分情况讨论 ss 前的系数是 11 还是 −1-1。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...