AtCoder AGC030-B题解报告

╰+哭是因爲堅強的太久メ 2022-03-27 09:39 155阅读 0赞

# 一、题目 #

[https://atcoder.jp/contests/agc030/tasks/agc030\_b][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

[https_atcoder.jp_contests_agc030_tasks_agc030_b]: https://atcoder.jp/contests/agc030/tasks/agc030_b
[1.png]: /images/20220327/08b78691e0304e8fb376407427bf3849.png