美团点评编程题（已更新）
c++版本 分析O（n） 如果0-i的值和0-j的值对k取余数，相同，则可以记录i+1到j这一段为k的倍数
其实空间复杂度可以更低一些
#include<iostream>
#include<memory.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[100001];
int cnt[100001][2];
memset(cnt,-1,sizeof(cnt));
long long int sum[100001];
//sum[0]=a[0];
for(int i=0;i<n;i++){
cin>>a[i];
if(i==0) sum[i]=a[i];
else sum[i]=a[i]+sum[i-1];
}
int k;
cin>>k;
int len=0;
for(int i=0;i<n;i++){
if(sum[i]%k!=0){
if(cnt[sum[i]%k][0]==-1){
cnt[sum[i]%k][0]=i;
}
else if(cnt[sum[i]%k][1]==-1){
cnt[sum[i]%k][1]=i;
if(len<i-cnt[sum[i]%k][0])
len=i-cnt[sum[i]%k][0];
}
else {
cnt[sum[i]%k][1]=i;
if(len<i-cnt[sum[i]%k][0])
len=i-cnt[sum[i]%k][0];
}
}
else {
if(len<i+1){
len=i+1;
}
}
}
cout<<len<<endl;
}
第二题，随意吧，n=30,只要思路对都能过
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int s[30];
for(int i=0;i<n;i++){
cin>>s[i];
}
int flag=0;
sort(s,s+n);
int sum=0;
if(s[n-1]==s[n-2]) flag=1;
for(int i=n-2;i>=0;i--){
sum+=s[i];
if(sum>s[n-1]) flag=1;
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
传音控股公司福利 327人发布