美团校招-K 的倍数-C++

K 的倍数

时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

序列中任意个连续的元素组成的子序列称为该序列的子串。
现在给你一个序列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 ≤ 𝑁 ≤ 105 。
第二行包含 N 个整数𝑝𝑖 ，𝑝𝑖 表示序列P第i个元素的值。0 ≤ 𝑝𝑖 ≤ 105 。
第三行包含一个整数 K， 1 ≤ 𝐾 ≤ 105 。
输出
输出一个整数ANS，表示答案。

样例输入

Input Sample 1
5
1 2 3 4 5
5
Input Sample 2
6
3 1 2 7 7 7
4

样例输出

Output Sample 1
5
Output Sample 2
5

#include <iostream>
using namespace std;
int main(){
   int n,k;
   int a[100000];
   int sum,c,max=0;
   cin>>n;
   for(int i=0;i<n;i++){
        cin>>a[i];
        cin>>k;
   }
   for(int i=0;i<n;i++) {    
       sum=a[i];
       for(int j=i+1;j<n;j++){ 
           sum=a[j]+sum;
           if((sum%k)==0) {
                c=j-i+1;
                if(c>max)
                 max=c;
              }
          }
    
    }
    cout<<max<<endl;
}

67%

解决方法1：

输入上万的题目 用scanf不要用cin

for(int i=0;i<n;i++){
    cin>>a[i];
    cin>>k;
}

vector<int> v; 
int x; 
for (int i=0; i<n; i++) { 
    scanf("%d",&x); 
    v.push_back(x); 
}

解决方法2：

程序加上

if(ans>n-i)//加了这句就不会超时
    break;

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
    int n,key;
    while(cin>>n)
    {
        int vec[100000];        
        for(int i=0;i<n;i++)
        {
            cin>>vec[i];
        }
        cin>>key;
        int ans=0;//满足条件的子串的最大长度
        for(int i=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=vec[j];
                if(sum%key==0)
                {
                    if(j-i+1>ans)
                        ans=j-i+1;
                }
            }
            if(ans>n-i)//加了这句就不会超时
                break;
        }
        cout<<ans<<endl;
    }
    return 0;
}