CodeForces 939C Convenient For Everybody(前缀和+滑动窗口)

2024-03-10 22:30

本文主要是介绍CodeForces 939C Convenient For Everybody(前缀和+滑动窗口),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题目描述

In distant future on Earth day lasts for n hours and that's why there are n timezones. Local times in adjacent timezones differ by one hour. For describing local time, hours numbers from 1 to n are used, i.e. there is no time "0 hours", instead of it "n hours" is used. When local time in the 1-st timezone is 1 hour, local time in the i-th timezone is i hours.

Some online programming contests platform wants to conduct a contest that lasts for an hour in such a way that its beginning coincides with beginning of some hour (in all time zones). The platform knows, that there are ai people from i-th timezone who want to participate in the contest. Each person will participate if and only if the contest starts no earlier than s hours 00 minutes local time and ends not later than f hours 00 minutes local time. Values s and f are equal for all time zones. If the contest starts at f hours 00 minutes local time, the person won't participate in it.

Help platform select such an hour, that the number of people who will participate in the contest is maximum.

输入格式:

The first line contains a single integer n (2 ≤ n ≤ 100 000) — the number of hours in day.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 10 000), where ai is the number of people in the i-th timezone who want to participate in the contest.

The third line contains two space-separated integers s and f (1 ≤ s < f ≤ n).

输出格式:

Output a single integer — the time of the beginning of the contest (in the first timezone local time), such that the number of participants will be maximum possible. If there are many answers, output the smallest among them.

题目翻译:

有n个时区,每个时区一天有n个小时。现在要举办一场持续1小时的比赛,开始时间与某个小时的开始时间一致。 在第i时区,有a[i]人参赛。

来自一个时区的人只会参加开始时间不早于当地时间s小时,结束时间不晚于当地时间f小时的比赛。

求出可以使得参赛人数最多的时间。

第一行,输入一个整数n(2≤n≤100000)。

第二行,输入n个整数(1≤ai​≤10000)。

第三行,输入两个整数,s和f。

思路:

设比赛在1时区的开始的时间为x,则如果i时区参赛,满足于以下条件:

1.s - i\leqslant x

2.f - i \geqslant x + 1

所以,参赛时区的区间为[s - x ,f - x - 1]

现在只需枚举x,并将对应区间中的参赛人数求和,即可寻找参赛人数的最大值。

可以进行前缀和优化,或者滑动窗口。

Code:

#include <iostream>
using namespace std;
const int N = 1e6 + 9;
int a[N], sum = 0, ans, maxv = 0;
int main() 
{int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i % n];int s, f;cin >> s >> f;//在s-f区间内选取人数for (int i = s; i <= f; i++) sum += a[i % n];for (int i = 0; i < n; i++) {//由于模可能取到0,所以 将其改到n即可int l = (s - i + n) % n;int r = (f - i + n) % n;sum += a[l] - a[r];if (sum > maxv) maxv = sum, ans = i;}cout << ans + 1 << endl;return 0;
}

这篇关于CodeForces 939C Convenient For Everybody(前缀和+滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/795720

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

主窗口的设计与开发(二)

主窗口的设计与开发(二) 前言         在上一集当中,我们完成了主窗口的初始化,主窗口包括了左中右三个区域。我们还完成了对左窗口的初始化,左窗口包括了用户头像、会话标签页按钮、好友标签页按钮以及好友申请标签页按钮。对于切换每个标签页,我们还做了初始化信号槽的内容。最后我们将整个MainWidget类设置为单例模式。         那么这一集我们将继续完成主窗口的设计与开发,这一集我