1358 - D. The Best Vacation (贪心+二分+前缀和)

爱被打了一巴掌 2021-07-16 11:43 351阅读 0赞

[题目][Link 1]

思路：贪心一下，要使拥抱次数最多必然是以每一个月的末尾为最后一天时，假设b(n-3) b(n-2) b(n-1) b(n) …c(1) c(2)… c(n)…a(n-4) a(n-3) 完后挪一个 b(n-2) b(n-1) b(n) …a(n-3) a(n-2) 当a(n-2)>b(n-3)时会使值增加，那么肯定继续挪到最后一个时a(n)最优。而a(n-2)<b(n-3)时我们往回挪使值增大，也挪到c(n)时最优。  
现在可以知道我们只需枚举每一个最后的点即可，再前缀和记录预处理一下，求每个截至时贪心比较即可得出答案，细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e6 + 5;
    int lst[Max];
    ll sx[Max], s[Max];
    
    int main()
    { 
    	ll n, x;cin >> n >> x;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> sx[i];sx[i + n] = sx[i];
    		s[i+n]=s[i] = (sx[i] + 1) * sx[i] / 2;
    	}
    	for (int i = 1;i <= 2*n;i++)
    	{ 
    		sx[i] = sx[i-1] + sx[i];s[i] = s[i-1] + s[i];
    	}
    	ll ans = 0;
    	for (int i = 1;i <= n * 2;i++)
    	{ 
    		if (sx[i] < x)continue;
    		ll low = sx[i] - x;
    		ll p = lower_bound(sx + 1, sx + 2 * n + 1, low) - sx;
    		if (x == sx[i] - sx[p])ans = max(ans, s[i] - s[p]);
    		else
    		{ 
    			ll dnum = low - sx[p - 1];
    			ans = max(ans, s[i] - s[p - 1] - (dnum + 1)*dnum / 2);
    		}
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforces.ml/contest/1358/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，351人围观）

还没有评论，来说两句吧...

相关阅读

相关 D. Non-zero Segments----前缀和

一维前缀和： sum\[0\] = 0; sum\[i\] = sum\[i-1\] + a

古城微笑少年丶/ 2022年11月19日 07:38/ 0 赞/ 149 阅读

相关 Slay the Dragon 二分 + 贪心

二分+贪心找到最小花费，主要是边界有点麻烦 // Problem: C. Slay the Dragon // Contest: Codeforces - E

柔情只为你懂/ 2022年09月12日 04:49/ 0 赞/ 132 阅读

相关 Don’t Skip Vacations for the Project

Don’t Skip Vacations for the Project Joe Zenevitch New York, New York, U.S. SoFTW

Dear 丶/ 2022年08月09日 06:15/ 0 赞/ 134 阅读

相关 POJ 3617 Best Cow Line【贪心】

Description FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual”Farmer of the

心已赠人/ 2022年06月04日 00:46/ 0 赞/ 142 阅读

相关二分查找+贪心-CodeForces 732D-Exams

二分查找+贪心-CodeForces 732D-Exams -------------------- 题目链接：[D. Exams][] 思路：

- 日理万妓/ 2022年05月17日 10:46/ 0 赞/ 219 阅读

相关 KMP-(HDU1358)Period[前缀中的周期]

KMP-(HDU1358)Period -------------------- 题目链接：[9:前缀中的周期][9] KMP基础：给个传

矫情吗；*/ 2022年05月17日 01:50/ 0 赞/ 168 阅读

相关 Best Cow Line POJ - 3617（贪心)

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competi

本是古典何须时尚/ 2022年03月10日 09:38/ 0 赞/ 166 阅读

相关 C. Letters （前缀和、二分查找）

题目链接：[http://codeforces.com/problemset/problem/978/C][http_codeforces.com_problemset_pro

浅浅的花香味﹌/ 2021年12月12日 09:39/ 0 赞/ 266 阅读

相关 AtCoder Beginner Contest 137 D - Summer Vacation——————贪心，优先队列

[abc137\_D - Summer Vacation][abc137_D - Summer Vacation] Problem Statement There a

雨点打透心脏的1/2处/ 2021年11月01日 08:14/ 0 赞/ 334 阅读

相关 1358 - D. The Best Vacation (贪心+二分+前缀和)

[题目][Link 1] 思路：贪心一下，要使拥抱次数最多必然是以每一个月的末尾为最后一天时，假设b(n-3) b(n-2) b(n-1) b(n) …c(1) c(2)

爱被打了一巴掌/ 2021年07月16日 11:43/ 0 赞/ 352 阅读