D. The Best Vacation（贪心+前缀和+二分）lifehappy-

The Best Vacation

思路

前缀和加贪心

贪心：我们的结尾点一定是在某一个月的最后一天。

贪心部分证明：我们选定两组数

$A = a_{n – 2}, a_{n – 1}, a_{n}, b_{1}, b_{2}, b_{3}……b_{n – 2}, b_{n – 1}$

A=an−2​,an−1​,an​,b1​,b2​,b3​……bn−2​,bn−1​

$B = a_{n – 1}, a_{n}, b_{1}, b_{2}, b_{3}……b_{n – 2}, b_{n – 1}, b_{n}$

B=an−1​,an​,b1​,b2​,b3​……bn−2​,bn−1​,bn​

假如我们的贪心策略是正确的，只需要证明
$b_{n} > a_{n – 2}$

bn​>an−2​即可，但是我们总能如愿吗，看一组样例。

2 4 5 2  1 2 3 4 5 1 2  chose 3 4 5 1 chose 4 5 1 2  显然这里贪心策略错了 ans 2 3 4 5 

但是我们能看到的是这组样例的却也是以某一个月的最后一天结尾。

我们列出
$a, b$

a,b两个月的每天来。

$a_{1}, a_{2}, a_{3}, ……, a_{n – 2}, a_{n – 1}, a_{n}$

a1​,a2​,a3​,……,an−2​,an−1​,an​

$b_{1}, b_{2}, b_{3}, ……, b_{n – 2}, b_{n – 1}, b_{n}$

b1​,b2​,b3​,……,bn−2​,bn−1​,bn​

假如
$b_{n} > a_{n – 2}$

bn​>an−2​，我们选定的两组数是一定成立的。

或者
$b_{n} < a_{n – 2}$

bn​<an−2​，同样的我们可以得到
$each i from 1 to n，a_{n – i – 1} > b_{n – i + 1}$

each i from 1 to n，an−i−1​>bn−i+1​

这里我们证明得到在上一步的贪心中，以月份
$a$

a结尾的是正确的，否则的话我们将得到以
$b$

b结尾的是正确的。

由此我们的贪心策略是正确的，所以我们只需要用前缀和来维护，然后通过枚举结尾点就行了。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 4e5 + 10;  ll a[N], s[N], x; int n; int main() { freopen("in.txt", "r", stdin);  ios::sync_with_stdio(false);     cin >> n >> x; for(int i = 1; i <= n; i++) {         cin >> a[i];         a[i + n] = a[i];         s[i] = s[i + n] = (1 + a[i]) * a[i] / 2; } for(int i = 1; i <= n << 1; i++)    a[i] += a[i - 1], s[i] += s[i - 1];     ll ans = 0; for(int i = 1; i <= 2 * n; i++) { if(a[i] < x) continue;         ll low = a[i] - x; int p = lower_bound(a + 1, a + 1 + 2 * n, low) - a; if(a[i] - a[p] == x)    ans = max(ans, s[i] - s[p]); else {             ll last = low - a[p - 1];             ans = max(ans, s[i] - s[p - 1] - (1 + last) * last / 2); } }     cout << ans << "n"; return 0; }