AcWing 3810. 最长连续休息时间

原题链接

题目描述

一天可以被分为 $n$ 个时段。

一个工人的每日工作安排可以用一个长度为 $n$ 的 $01$ 序列 $a_1,a_2,…,a_n$ 来表示。

$a_i$ 为 $0$ 表示第 $i$ 个时间段是工作时间， $a_i$ 为 $1$ 表示第 $i$ 个时间段是休息时间。

工人日复一日的严格按照这个工作安排来进行工作和休息。

请问，工人的最长连续休息时间有多长（单位：时段）？

注意，连续休息时间可能跨天。

保证工人至少在一个时间段处于工作状态。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$ 。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ 。

输出格式

每组数据输出一行结果，表示最长连续休息时间。

数据范围

$1≤T≤10$ ,
$1≤n≤2×10^5$ ,
$0≤a_i≤1$ ,
同一测试点内所有 $n$ 的和不超过 $2×10^5$ 。

样例

输入样例：

4
5
1 0 1 0 1
6
0 1 0 1 1 0
7
1 0 1 1 1 0 1
3
0 0 0

输出样例：

思路

工人日复一日的严格按照这个工作安排来进行工作和休息。就是说，可能还要算上后一天的开头休息时间，题目保证至少在一个时间段处于工作状态，那么只要给数组复制一遍即可。可以不用复制数组，只要遍历一遍数组后，让指针从头再遍历一遍即可。

然后问题就变成了：求数组的子数组全为 $1$ 的最大长度。

代码

C++

#include <iostream>

using namespace std;

const int N = 2e5 + 5;
int a[N];

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n;
        cin >> n;
        for ( int i = 0; i < n; i ++ ) cin >> a[i];
        int res = 0;
        for ( int i = 0; i < 2 * n; i ++ )
        {
            int j = i;
            while ( j < 2 * n && a[j % n] ) j ++;
            res = max(res, j - i);
            i = j;
        }
        cout << res << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static final int N = (int) (2 * 1e5) + 5;
    static int a[] = new int[N];
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            int n = in.nextInt();
            for ( int i = 0; i < n; i ++ ) a[i] = in.nextInt();
            int res = 0;
            for ( int i = 0; i < 2 * n; i ++ )
            {
                int j = i;
                while ( j < 2 * n && a[j % n] == 1 ) j ++;
                res = Math.max(res, j - i);
                i = j;
            }
            System.out.printf("%d\n", res);
        }
    }
    
}