Codeforces Round #645 (Div. 2)D. The Best Vacation
假設:一年有n個月,第i個月有d[i]天,每個月是從1号開始到d[i]号,即1,2,3…d[i]号。設某月的某天是s号,就可以獲得s個hug擁抱。
輸入一個x,你需要從這中選出連續的x天,使得其獲得的hug擁抱數量最大。
需要注意是的這連續的x天中可以有下一年的天數,也就是說這裡可以構成一個環,故可以預處理第二年的月份天數,即d[i+n]=d[i]。
題解:
最有解的最後一天肯定某月份的月底。
字首和預處理每個月份的天數,
找出連續的x天,
利用二分找出滿足連續x的的月份,還需要考慮最開始的一個月隻取了一部分。
再字首和數組減出區間和,貪心比較每次的獲得hug擁抱數量即可。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define _for(i,a,b) for(int i = (a);i<(b);i++)
#define endl '\n'
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
const int MAX=1e6+7;
ll a[MAX],sum_day[MAX],sum_hug[MAX];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,x;cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++)
{
sum_day[i]+=a[i]+sum_day[i-1];
sum_hug[i]+=a[i]*(a[i]+1)/2+sum_hug[i-1];
}
ll ans=0;
for(int i=1;i<=2*n;i++)
{
if(sum_day[i]>=x)
{
int p=lower_bound(sum_day+1,sum_day+2*n+1,sum_day[i]-x)-sum_day;
ll res=sum_day[p]-(sum_day[i]-x);
ll last=(a[p]+a[p]-res+1)*res/2;
ans=max(ans,last+sum_hug[i]-sum_hug[p]);
}
}
cout<<ans<<endl;
}