P3131 [USACO16JAN] Subsequences Summing to Sevens S

题目描述

Farmer John's NN cows are standing in a row, as they have a tendency to do from time to time. Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic childhood incident involving the numbers 1…61…6, he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.

Please help FJ determine the size of the largest group he can photograph.

给你n个数，分别是a[1],a[2],...,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

输入格式

The first line of input contains NN (1≤N≤50,0001≤N≤50,000). The next NN

lines each contain the NN integer IDs of the cows (all are in the range

0…1,000,0000…1,000,000).

输出格式

Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7. If no such group exists, output 0.

输入输出样例

输入 #1复制

7
3
5
1
6
2
14
10

输出 #1复制

5

说明/提示

In this example, 5+1+6+2+14 = 28.

import java.util.Scanner;

public class Main {
    // 这里可以根据需要定义一个相对较大的数，模拟C++中的maxn，不过Java中可以根据实际输入动态分配空间
    public static final int MAXN = 50010;
    static int[] pre = new int[MAXN];
    static int n;
    static int mx = -1;
    static int[] first = new int[7];
    static int[] last = new int[7];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            pre[i] = scanner.nextInt();
            pre[i] = (pre[i] + pre[i - 1]) % 7;
        }

        // 倒着遍历找第一次出现余数的位置
        for (int i = n; i >= 1; i--) {
            first[pre[i]] = i;
        }
        first[0] = 0;

        // 正着遍历找最后一次出现余数的位置
        for (int i = 1; i <= n; i++) {
            last[pre[i]] = i;
        }

        // 遍历余数情况，找最大长度
        for (int i = 0; i <= 6; i++) {
            mx = Math.max(last[i] - first[i], mx);
        }

        System.out.println(mx);

        scanner.close();
    }
}

原文地址：https://blog.csdn.net/qq_74794797/article/details/144302777

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！