题解 CF939C 【Convenient For Everybody】

Caro23333 · 2018-02-25 21:52:50 · 题解

本蒟蒻的第一篇题解（而且还是道水题

在此不对题意做解释。 据题意，由于最后一个时区和第一个时区是连续的，所以当比赛举办者确立比赛时间在第一个时区为i时，任意一个时区j的时间为(j+i-1)%n.经过推理可以知道此时能够参加比赛的时区有如下三种情况：

i<=s 从s-i+1时区到f-i时区可以参加

s<i<f 从1到f-i时区和s-i+n+1到n时区可以参加

i>=f 从s-i+n+1时区到f-i+n时区可以参加

由于每个时区的人数是固定的，所以使用前缀和来维护人数的和。

代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 100005;
int n,s,f;
int a[MAXN],pre[MAXN];
int main()
{
    cin >> n;
    for(int i = 1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        pre[i] = pre[i-1]+a[i]; //维护前缀和
    }
    cin >> s >> f;
    int ans = 0, maxa = 0;
    for(int i = 1; i<=n; i++)
    {
        int tmp;
        if(i<=s) tmp = pre[f-i]-pre[s-i]; //第一种情况
        else if(i<=f) tmp = pre[f-i]+pre[n]-pre[s-i+n]; //第二种情况
        else tmp = pre[f-i+n]-pre[s-i+n]; //第三种情况
        if(tmp>maxa)
        {
            ans = i;
            maxa = tmp;
        }
    }
    cout << ans << endl;
    return 0;
}