Codeforces Round #645 (Div. 2) 重点：D：The Best Vacation

题目链接：点这里

D. The Best Vacation

题意：一年有n个月，每个月有di天，给你len天假期，如果在每个月的第j天拜访他人就会获得j个拥抱，让你最大化拥抱。
解题思路：主流思路叫做双指针，但是不是双指针的那种典型的写法。首先做这道题之前需要证明一下，假期选择天数的结尾一定是每个月的结尾天数。这是个非典型推论，我们来证明一下，首先上一下cf的证明
首先使用的是反证法，首先设结尾为x，结尾的右边是x+1（因为如果不是这样的话，结尾就是月份的结尾）现在想使左移的值大于右移的值，那么若成立，便可以一直左移，所以不是最优解；
既然知道了一定是在月末买，那我们可以轻松知道往前二分查找起点再把溢出的天数加一加，便可一切明了。
主要还是难在月末这个点 的贪心。

LL a[N];
int main(){
    int n ;
    LL len ;
    while(~scanf("%d %lld", &n , &len)){
        for(int i = 1; i <= n ; i ++){
            scanf("%lld" ,&a[i]);
            a[i+n] = a[i];
        }
        n *= 2;
        vector<LL> B={0},C={0};
        for(int i = 1; i <= n ;i ++){
            B.pb(B.back()+a[i]);
            C.pb(C.back()+a[i]*(a[i]+1)/2);
        }
        LL ans = 0;
        for(int i = 0 ; i < n ; i ++){
            if(B[i+1] >= len){
                int pos = upper_bound(B.begin(),B.end(),B[i+1]-len) - B.begin();
                LL cnt = C[i+1] - C[pos];
                LL day = B[i+1] - B[pos];
                LL more =  len - day;
                cnt += (a[pos]*(a[pos]+1)/2);
                cnt -= ((a[pos] - more)*(a[pos] - more + 1)/2);
                ans = max(ans, cnt);
            }
        }
        printf("%lld\n",ans);
    }
 
}