题意：有n个月 每个月d天 日期是1 2 3 ……d 给x天 问从哪天开始走，走x天 日期的和最大
可以从今年跨越到明年
题目链接：https://codeforces.ml/contest/1358/problem/D
思路：首先要考虑到 取到最大值的时候结尾必须要在每个月的月底那天
于是可以考虑枚举每个月底 因为这是个环 所以拼接n天在n天之后
然后从n+1枚举到2n 看哪一天可以去得到最大
然后用前缀和维护 二分查询 时间复杂度o(nlogn)
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define pb push_back 5 const int maxn =2e5+10; 6 ll d[maxn*2]; 7 ll sum[maxn*2]; 8 ll h[maxn*2]; 9 int main() 10 { 11 ios::sync_with_stdio(false); 12 cin.tie(0); 13 ll n,x; 14 cin>>n>>x; 15 for(int i=1;i<=n;i++) 16 { 17 cin>>d[i]; 18 d[i+n]=d[i]; 19 } 20 for(int i=1;i<=n*2;i++) 21 { 22 sum[i]=sum[i-1]+d[i]; 23 h[i]=h[i-1]+(d[i]*(d[i]+1))/2; 24 } 25 ll max1=-1; 26 for(int i=n+1;i<=2*n;i++) 27 { 28 ll res=0; 29 int p=lower_bound(sum+1,sum+2*n+1,sum[i]-x)-sum; 30 res+=h[i]-h[p];//拥抱度 31 ll t=sum[p]-(sum[i]-x);//剩多少天 32 res+=(d[p]-t+1)*t+(t*(t-1))/2;//等差数列求和 33 max1=max(max1,res); 34 } 35 cout<<max1<<‘\n‘; 36 37 38 39 }
Codeforces Round #645 (Div. 2) D. The Best Vacation
原文：https://www.cnblogs.com/winfor/p/12981757.html
