1.样例解释

由于样例 2 和 3 没有给出解释，作者做这题时，对着样例思考了很久，故~~作者太菜了~~在这里给出样例解释。样例 1 和 4 答案显然，不作解释。

1-1.样例 #2

样例输入：

CPP

6 3
-4 -2 2 6 8 9

样例输出：

CPP

样例解释：最优的方法如下（下表中

a,b

的意义与原题一致，

A

数组即为原题中输入的镜子位置，初始令

a = s

，

s

的意义见原题）。

顺序	使用镜子编号	镜子的位置（ $b$ ）	此时答案( $2b - a$ )
$\bm1$	$1$	$A[1] = -4$	$2 \times (-4) - 3 = -11$
$\bm2$	$6$	$A[6] = 9$	$2 \times 9 - (-11) = 29$
$\bm3$	$2$	$A[2] = -2$	$2 \times (-2) - 29 = -33$
$\bm4$	$5$	$A[5] = 8$	$2 \times 8 - (-33) = 49$
$\bm5$	$3$	$A[3] = 2$	$2 \times 2 - 49 = -45$
$\bm6$	$4$	$A[4] = 6$	$2 \times 6 - (-45) = 57$

最终答案为

57

。

1-2.样例 #3

样例输入：

CPP

9 9
0 1 3 3 4 5 8 9 10

样例输出：

CPP

样例解释：最优的方法如下（下表中

a,b

的意义与原题一致，

A

数组即为原题中输入的镜子位置，初始令

a = s

，

s

的意义见原题）。

顺序	使用镜子编号	镜子的位置（ $b$ ）	此时答案( $2b - a$ )
$\bm1$	$9$	$A[9] = 10$	$2 \times 10 - 9 = 11$
$\bm2$	$1$	$A[1] = 0$	$2 \times 0 - 11 = -11$
$\bm3$	$8$	$A[8] = 9$	$2 \times 9 - (-11) = 29$
$\bm4$	$2$	$A[2] = 1$	$2 \times 1 - 29 = -27$
$\bm5$	$7$	$A[7] = 8$	$2 \times 8 - (-27) = 43$
$\bm6$	$3$	$A[3] = 3$	$2 \times 3 - 43 = -37$
$\bm7$	$6$	$A[6] = 5$	$2 \times 5 - (-37) = 47$
$\bm8$	$4$	$A[4] = 3$	$2 \times 3 - 47 = -41$
$\bm9$	$5$	$A[5] = 4$	$2 \times 4 - (-41) = 49$

最终答案为

49

。

2.题目思路

由于题目要求求出最大值，故考虑贪心。

当我们看懂样例时，我们就大致明白了贪心的方法（为了方便解释，下文中将“角色的位置移动到以镜子为中心的对称点”简称为“跳跃”）：从初始位置开始，找到最后一个镜子向右跳跃一步，找到最前一个镜子向左跳跃一步，两者交替进行。

但是，观察两个样例发现，两组样例的最优解第一步选择了相反的方向“跳跃”！

观察子任务的特殊性质，我们发现：子任务中出现了“

N

为偶数”限制，这启发我们将本题分类讨论，以

N

的奇偶性来讨论。

当

N

为偶数时，最优方法为先向左，再向右，如此交替进行，这样答案就会先变小后变大，当

\dfrac{N}{2}

次交替“跳跃”结束后，答案必然为最大值。

当

N

为奇数时，最优方法为先向右“跳跃”一次，再进行

\dfrac{N - 1}{2}

次交替“跳跃”，如果不先向右，那么最终答案必然在镜子左侧，错误。

我们可以用一个布尔变量记录当前是否要向右“跳跃”（记录是否向左也可），再用两个指针分别记录左右两侧当前使用的镜子编号。如果布尔变量值为真，则记录右侧编号的指针左移一个，否则记录左侧编号的指针右移一个。由于每个镜子只能用一次，故答案循环

N

次即可。

时间复杂度

\mathcal O(N)

。

3.贪心算法的正确性

我们感性理解一下。

要求答案最大，即求

a,b

，使“跳跃”完成后

2b - a

最大。

要使上述式子最大，需要使

b

最大，

a

最小。要想使

a

最小，就需要使上一个

2b - a

的结果（这个结果会是新的

a

）最小，于是就尝试往左边最前一个镜子“跳跃”，要想使上一个

2b - a

最小，就要使

b

最小，

a

最大。要想使

a

最大，就需要使上上一个

2b - a

的结果最大，于是尝试往右边最后一个镜子“跳跃”……以此类推

N

次，可以发现如果每步都是最优，最终得到的一定是最优解。

4.代码及注意问题

程序时间优化技巧

当输入量较大时，使用快读（见代码）；
使用 $\texttt{<<1}$ 代替 $\texttt{*2}$ ；
使用 $\texttt{if(n\&1)}$ 代替 $\texttt{if(n\%2==1)}$ 。

代码

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=200005;
int n,s,a[max_n],l,r;
bool toright;
long long ans; //开 long long！
inline int read(){ //快读
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read(),s=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    if(n&1){ //特判奇数，此时要先向右跳。n&1 可以快速判断 n 是否为奇数，是竞赛常用方法。
        toright=true;
    }
    l=1,r=n;
    ans=s;
    for(int i=1;i<=n;i++){
        if(toright){
            ans=(a[r]<<1)-ans; //<<1 相当于 *2，但更快
            r--; //指针向左移 1 个
        }
        else{
            ans=(a[l]<<1)-ans; //<<1 相当于 *2，但更快
            l++; //指针向右移 1 个
        }
        toright=!toright; //对原先的布尔值取反（即 true 变为 false，或 false 变为 true）。
    }
    printf("%lld\n",ans);
    return 0;
}

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

文章操作