本文主要是介绍Codeforces Round #464 Convenient For Everybody 思维,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Convenient For Everybody
题意:
将一天分为 n 个小时,所以有 n 个时区(当第一个时区的时间为1时,第 i 个时区则为 i 时)。现在要举办一场比赛(比赛的时间为 1 个小时)给你每个时区参赛的人数 a ,和一个时间段 s~f,当地时间不小于 s 且小于 f 的时间可以参加比赛。求参赛人数最多时最小的开始时间(第一个时区的时间) 。
题解:
一共可以有 m=f-s 个时区的人可以参加比赛。
在这个问题中,需要定义一个“标准时间”(Standard Time),之后将所有的“本地时间”折算成“标准时间”。
可以假设一个虚拟的0时区,将这个时区的时间定义为“标准时间”。于是:当0时区的“本地时间”(即“标准时间”)为0时,i 时区的“本地时间”为 i 。
设赛事开始的“标准时间”为x,于是:若 i 时区参赛,则有:
①x+i s => s-i ≤ x;
②f > x+i => f-i > x;
于是,参赛时区 区间为[s-x,f-x-1]或[s-x,f-x)。只需枚举x,并将对应区间中的参赛人数求和,即可寻找参赛人数的最大值。可以考虑前缀和,或者滑动窗口(注:窗口的滑动方向应该是循环向左的)。
参考博客:https://www.cnblogs.com/siuginhung/p/8452987.html
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int a[maxn];
int main()
{int n;int s,f;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i%n]);scanf("%d%d",&s,&f);int sum = 0;for(int i = s+1 ; i <= f; i++) // 选出 f-s 个时区sum += a[i%n]; //i 从 s+1 开始便于与枚举时 选出相应的区间int k = 0,ma = 0;for(int i = 0 ; i < n ; i++ ) //枚举标准时区对应的时间{int l = (s-i+n)%n; int r = (f-i+n)%n;sum -= a[r];sum += a[l];if(sum > ma){ma = sum;k = i;}}printf("%d\n",k+1);return 0;
}
这篇关于Codeforces Round #464 Convenient For Everybody 思维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!