The Best Vacation

思路

前綴和加貪心

貪心：我們的結尾點一定是在某一個月的最后一天。

貪心部分證明：我們選定兩組數

$A=a_{n?2},a_{n?1},a_n,b_1,b_2,b_3\dots \dots b_{n?2},b_{n?1}$

$B=a_{n?1},a_n,b_1,b_2,b_3\dots \dots b_{n?2},b_{n?1},b_n$

假如我們的貪心策略是正確的，只需要證明$b_n>a_{n?2}$即可，但是我們總能如愿嗎，看一組樣例。

2 4 5 21 2 3 4 5 1 2chose 3 4 5 1 chose 4 5 1 2顯然這里貪心策略錯了 ans 2 3 4 5

但是我們能看到的是這組樣例的卻也是以某一個月的最后一天結尾。

我們列出$a,b$兩個月的每天來。

$a_1,a_2,a_3,\dots \dots ,a_{n?2},a_{n?1},a_n$

$b_1,b_2,b_3,\dots \dots ,b_{n?2},b_{n?1},b_n$

假如$b_n>a_{n?2}$，我們選定的兩組數是一定成立的。

或者$b_n<a_{n?2}$，同樣的我們可以得到$eachifrom1ton，a_{n?i?1}>b_{n?i+1}$

這里我們證明得到在上一步的貪心中，以月份$a$結尾的是正確的，否則的話我們將得到以$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; }

總結

以上是生活随笔為你收集整理的D. The Best Vacation（贪心+前缀和+二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。