题解：P11963 [GESP202503 六级] 环线

· · 题解

前言

提供一种考场上想到的线段树乱搞解法。

题目简介

一个环上有 n 个点，第 i 个点权值为 a_i，当你来到一个点，就能取得这个点的权值。问：在最多绕一圈（经过 n 个点）的情况下所能取到的最多的权值。

题解

先考虑暴力做法：

先断环为链，并维护一个前缀和数组 sum，枚举两个点 i,j，保证 1 \le i < j \le 2n，找出 sum_j-sum_i 的最大值即可。时间复杂度 O(n^2)。

这样显然会超时。考虑优化：

不难看出，在 sum_i 一定时，sum_j 越大，结果就越大，也就越有可能冲击最优解。又因为 i < j \le 2n，所以 sum_j-sum_i 的最大值就是 \max_{i < j \le 2n} sum_j -sum_i。于是问题就变成了寻找区间最大值，可以用线段树在 O(\log n) 的时间内解出。这样，总的时间复杂度就变成了 O(n \log n)，可以通过。

最后还有一点：不要忘记开 long long！