美团点评——K的倍数

我不是女神ヾ 2022-06-09 10:29 226阅读 0赞

**题目描述：**

序列中任意个连续的元素组成的子序列称为该序列的子串。

现在给你一个序列P和一个整数K，询问元素和是K的倍数的子串的足底啊长度。

比如序列\[1,2,3,4,5\]，给定的整数为5，其中满足条件的子串为\{5\}、\{2,3\}、\{1,2,3,4\}、\{1,2,3,4,5,\}，那么答案就为5，因为最长的子串为\{1,2,3,4,5\}；如果满足条件的子串不存在，就输出0.

**输入：**

第一含一个整数N，1<=N<=10^5.

第二行包含N个整数Pi，Pi表示序列P第i个元素的值。0<=Pi<=10^5.

第三行包含一个整数K，1<=K<=10^5.

**输出：**

输出一个整数ANS，表示答案。

**样例输入：**

Input Sample 1

1 2 3 4 5

Input Sample 2

3 1 2 7 7 7

**样例输出：**

Output Sample 1

Output Sample 2

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
           int n;
           cin >> n;
           vector<int>arr(n);
           for (int i = 0; i<n; i++)
                  cin >> arr[i];
           int k;
           cin >> k;
           int maxlen = 0;
           int flag = 0;
           for (int i = n - 1; i >= 0; i--) {
                  for (int j = 0; j + i < n; j++) {
                         int sum = 0;
                         for (int m = j; m <= j + i; m++) {
                               sum += arr[m];
                         }
                         if (sum % k == 0) {
                               maxlen = i;
                               flag = 1;
                               break;
                         }
                  }
                  if (flag == 1)
                         break;
           }
           if (flag == 1)
                  cout << maxlen + 1 << endl;
           else
                  cout << 0 << endl;
           return 0;
    }