一、题目

https://atcoder.jp/contests/agc030/tasks/agc030_b

二、分析

1.png

如上图所示，0是Takahashi的住处。1，2，3，4，5是五棵树的位置。对于每棵树，都有逆时针和顺时针两个方向。
（1）逆时针到达第1棵树所能经过的最大距离为0（逆时针）-> 2（顺时针）-> 1，顺时针到达第1棵树所能经过的最大距离为0（顺时针）-> 1。
（2）逆时针到达第2棵树所能经过的最大距离为0（逆时针）-> 1（顺时针） -> 3（逆时针） -> 2，顺时针到达第2棵树所能经过的最大距离为0（顺时针） -> 3（逆时针） -> 1（顺时针）-> 2。
（3）逆时针到达第3棵树所能经过的最大距离为0（逆时针）-> 1（顺时针） -> 5（逆时针）-> 2（顺时针）-> 4（逆时针）-> 3，顺时针到达第3棵树所能经过的最大距离为0（顺时针） -> 5（逆时针） -> 1（顺时针）-> 4（逆时针） -> 2（顺时针） -> 3（逆时针）。
（4）逆时针到达第4棵树所能经过的最大距离为0（逆时针）-> 3（顺时针） -> 5（逆时针） -> 4，顺时针到达第4棵树所能经过的最大距离为0（顺时针） -> 5（逆时针） -> 3（顺时针）-> 4。
（5）逆时针到达第5棵树所能经过的最大距离为0（逆时针）-> 5，顺时针到达第5棵树所能经过的最大距离为0（逆时针）-> 4（顺时针） -> 5。
上面计算出N * 2 = 5 * 2 = 10个距离，找出最大值即为所求。

在计算距离之前，要计算：①逆时针经过每一棵树并返回到原点的累积距离，存到l数组中；②顺时针到达每一棵树并返回原点的累积距离，存到r数组中。
而后计算总距离时，哪一棵树没有经过，就要把相应的距离减掉。
以逆时针经过第2棵树为例，经过的距离为X[2] + l[1]+ r[3] – 从0点到第4棵树的往返距离 – 从0点到第5棵树的往返距离。
具体可看下面的代码。

三、AC代码

#include <bits/stdc++.h>typedef long long ll;using namespace std;int L, N, X[200000];ll r[200001], l[200001], MAX;int main(){    cin >> L >> N;    for (int i = 0; i < N; ++i)    {        cin >> X[i];    }    for (int i = 0; i < N; ++i)    {        // 逆时针，不是当前树的往返距离，而是累积当前经过的所有的树的往返距离        l[i + 1] = l[i] + X[i] * 2;    }    for (int i = N - 1; i >= 0; --i)    {        // 顺时针，不是当前树的往返距离，而是累积当前经过的所有的树的往返距离        r[i] = r[i + 1] + (L - X[i]) * 2;    }    for (int i = 0; i < N; ++i)    {        // 逆时针，左右两棵树一定会到达        ll cnt = X[i] + l[i] + r[i + 1];        if (i >= N - (i + 1))        {            // 当前树的位置大于等于N的一半，要减去经过但没停下来的树            cnt -= l[i - (N - (i + 1))];        }        else        {            // 当前树的位置小于N的一半，要减去经过但没停下来的树            cnt -= r[i + 1 + i + 1];        }        MAX = max(MAX, cnt);        // 顺时针，与逆时针情景相似        cnt = L - X[i] + l[i] + r[i + 1];        if (i <= N - (i + 1))        {            cnt -= r[i + 1 + i];        }        else        {            cnt -= l[i - (N - (i + 1)) - 1];        }        MAX = max(MAX, cnt);    }    cout << MAX << endl;    return 0;}

TopCoder & Codeforces & AtCoder交流QQ群：648202993