美团点评2018校招在线考试-编程题一

发表于 | 分类于 ，

题目

描述

序列中任意个连续的元素组成的子序列称为该序列的子串。
现在给你一个序列P和一个整数K，询问元素和是K的倍数的子串的最大长度。
比如序列[1,2,3,4,5]，给定的整数 K 为 5，其中满足条件的子串为{5}、{2,3}、{1,2,3,4}、{1,2,3,4,5}，
那么答案就为 5，因为最长的子串为{1,2,3,4,5}；如果满足条件的子串不存在，就输出 0。

输入

第一含一个整数N, 1 ≤ N ≤ 105 。
第二行包含 N 个整数pi ，pi 表示序列 P 第 i 个元素的值。0 ≤ pi ≤ 105 。
第三行包含一个整数 K， 1 ≤ K ≤ 105 。

输出

只有一行,输出元素和是K的倍数的子串的最大长度。

Example

Input

5
1 2 3 4 5
5
6
2 1 7 7 7 7
4

Output

5
5

题解

思路

  • 求出 p1…pi(1 <= i <= n)的和,并 mod k,
  • 对于每个余数 s(0 <= i < k), 求出其第一次出现位置,求出其最后一次出现的位置,两者之间元素之和即能整除 k
  • 所求即两者之差中的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;

int n,arr[100001],k,first[100001],last[100001];
int main(int argc, const char * argv[])
{
    int i,j,maxlen;
    while(scanf("%d",&n)!=EOF)
    {
        first[0]=last[0]=arr[0]=0;
        maxlen=0;
        for(i=1;i<=n;++i)
        {
            scanf("%d",&arr[i]);
            if(i)
                arr[i]+=arr[i-1];
        }
        scanf("%d",&k);
        for(i=1;i<k;++i)
            first[i]=last[i]=-1;
        maxlen=0;
        for(i=1;i<=n;++i)
        {
            arr[i]%=k;
            if(first[arr[i]]<0)
                first[arr[i]]=i;
            else
                maxlen=max(maxlen,i-first[i]);
        }last[0]-first[0];
        cout<<maxlen<<endl;
    }
}