美团后台开发的编程题;
发布于 2017-08-31 21:19 2821 次浏览 2 赞 来自 试题交流  


// 第一题
int main() {
    int n, k;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> k;
    int s = accumulate(arr.begin(), arr.end(), 0);
    int m = 0;
    for(int hi = n - 1;hi>=0;hi--)
    {
        int sb = s, lo = 0;
        while(lo <= hi && (hi - lo + 1) > m){
            if (sb % k == 0) {
                m = hi - lo + 1;
                break;
            }
            sb -= arr[lo];
            lo++; 
        }
        s -= arr[hi];
    }
    cout << m;
}

// 第二题
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int m = *max_element(arr.begin(), arr.end());   
    int s = accumulate(arr.begin(), arr.end(), 0);
    if (m * 2 > s) {
        cout << "No";
    } else {
        cout << "Yes";
    }
}


13 条回复

兄弟,第一题n2会超时吧

2017-08-31 21:29

用的暴力求解,只通过33%,想看正确答案


import java.util.Scanner;

public class meituanOne {


public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

int N = sc.nextInt();

int [] arr=new int[N];

int i = 0;

while(sc.hasNext()&&i<N){

arr[i] = sc.nextInt();

i++;

}

int K=sc.nextInt();

int j = 0,k = 0,sum = 0,ANS = 0;

for (i=0;i<=N;i++){

for(j = 0;j+i<=N;j++){

                sum = 0;

for(k=0;k<i;k++){

sum+=arr[j+k];

}

if(sum%K == 0){

ANS = i;

}

}

}

System.out.println(ANS);

}

}


2017-08-31 21:31
coder_U35edSsg 回复 coder_725WY7PZ

一开始我随便写了个O(n^2)的超时, 后面换了一下遍历顺序过了, 题目的test case有问题吧; 不是按照最坏情况来的

2017-08-31 21:33
coder_U35edSsg 回复 ε 路人假゛

当 N - i 小于 ANS的时候就可以break了, 估计就能AC了

2017-08-31 21:36

第一题

6

1 5 2 4 3 6

6

结果为5,你的代码结果为4

2017-08-31 21:45
coder_725WY7PZ 回复 ε 路人假゛

我的思路是按k做,开一个数组长度是k。首先计算sum[i]=array[0]+…+array[i],然后记录min[sum[i]%k]=i,对每一个sum[j]%k计算j-min[sum[j]%k]。也就是说如果sum[i]和sum[j]对k取余相同,说明从array[i+1]到array[j]这一段的和是k的倍数。这样时间复杂度是n。

2017-08-31 21:46
ε 路人假゛ 回复 coder_U35edSsg

没懂,可能我写的代码比较糙,i是子串的个数,j是子串的起始位置, 那 N-i是数列除了子串的剩余个数,和ANS比较 是什么意思啊

2017-08-31 21:47
coder_U35edSsg 回复 coder_6JDTQYGQ

for循环里少加了一个( hi + 1> m)条件; 提交的时候加的

2017-08-31 21:47
coder_6JDTQYGQ 回复 coder_U35edSsg

加了条件也不对

完整代码是什么

2017-08-31 21:50
ε 路人假゛ 回复 coder_6JDTQYGQ

1 +5+2+4+3=15 ;5+2+4+3+6=20 都不是6的倍数啊,题目中说的是连续的

2017-08-31 21:51

第一题是求最长字串吗?

2017-08-31 22:32

你的输入里面有n,可是题目的输入只有k呀,如何能够在不输入数组元素个数的情况下,输入一个不定长的数组。

2017-09-01 10:05

这是AC的代码吗?

2017-09-04 16:48
添加回复
回到顶部