美团笔试2

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

备注

美团笔试每次都能教育人,太难了。

第一题

输入n,k,然后输入n个数字,数字为0代表Alis的房子可能出现在这里,数字非0代表其他的房子(数字的值就是价格),你要买一个房子,然后距离Alis的房子的期望距离最近。

题目出锅了,我暴力枚举,但是一直wa,wa了半个小时了实在是不敢相信,然后切到了第二题,写到一半难受,一想到我连第一题都过不了我就难受,我又来回马枪,杀回第一题,然后还是wa,最后狠心决定把第一题丢了算了,来来回回浪费了不少时间,还是一直没过,最后切完第三题的时候,笔试也快结束了,才发现出现了一个公告,说第一题如果有多个答案输出最小的那个,我把第27行改成<就过了

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 main(){
int n,k;
cin>>n>>k;
vector<int> mayHomePlace;
vector<int> canChoose;
vector<int> idx;
for(int i=0;i<n;i++){
int ai;
cin>>ai;
if(ai==0){
mayHomePlace.push_back(i);
}
if(ai!=0 && ai<=k){
canChoose.push_back(i);
}
}
int ans=0,d=1e9;
for(int i=0;i<canChoose.size();i++){
int x = canChoose[i];
int sum = 0;
for(int y:mayHomePlace){
sum+=abs(y-x);
}
if(sum<=d){
ans=x;
d=sum;
}
}
cout<<ans+1<<endl;
}

第二题

给你一个01串,你能删除三个连续的字符,可以无限次操作,问如何操作后让0和1的个数差最大,输出最大的差值。

使用dp即可dp0[x]代表前x个字符0-1最大的差值, dp1[x]代表前x个字符1-0的最大差值。

(果然还是太久没刷题了,都一年多没写过题了,dp方程我推了很久),最开始推出来是这样,然后一直wa27

1
dp0[i] = max(dp0[i-3],dp0[i-3]+cal(s[i],s[i-1],s[i-2]));

最后发现正确的转移方程是这个

1
2
3
4
5
dp0[i] = max(dp0[i-3],
dp0[i-3]+cal(s[i],s[i-1],s[i-2]),
dp0[i-2]+cal(s[i],s[i-1]),
dp0[i-1]+cal(s[i])
);
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include<bits/stdc++.h>
using namespace std;

int cal(char x){
return x=='0'?1:-1;
}

int cal(char x,char y){
return cal(x)+cal(y);
}

int cal(char x,char y,char z){
return cal(x)+cal(y,z);
}

int max(int a,int b,int c,int d){
return max(max(a,b),max(c,d));
}
// 0-1
int cal(int n,string s){
vector<int>dp0(s.size());
vector<int>dp1(s.size());

int ct=0;
for(int i=0;i<3&&i<s.size();i++){
if(s[i]=='0'){
ct++;
}else{
ct--;
}
dp0[i] = ct;
dp1[i] = -ct;
if(i==2){
dp0[i] = max(ct,0);
dp1[i] = max(-ct,0);
}
}

for(int i=3;i<s.size();i++){
dp0[i] = max(dp0[i-3],
dp0[i-3]+cal(s[i],s[i-1],s[i-2]),
dp0[i-2]+cal(s[i],s[i-1]),
dp0[i-1]+cal(s[i])
);
dp1[i] = max(dp1[i-3],
dp1[i-3]-cal(s[i],s[i-1],s[i-2]),
dp1[i-2]-cal(s[i],s[i-1]),
dp1[i-1]-cal(s[i])
);
}
return max(dp0.back(),dp1.back());
}

int main(){
int n;
cin>>n;
string s;
cin>>s;
cout<<cal(n,s)<<endl;
}


第三题

有两个射箭队伍,你是裁判,规定射箭射中后,射击的距离在d之内得1分,在d之外得2分,如何设计d的值,让一个队伍尽可能的领先分数。

暴力枚举d即可,计算得分的时候用upper_bound二分一下

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
#include<bits/stdc++.h>
using namespace std;

int cal(int d,vector<int>&v){
int lw = upper_bound(v.begin(),v.end(),d)-v.begin();
return lw+(v.size()-lw)*2;
}

int main(){
int n,m;
cin>>n>>m;
vector<int> a(n),b(m);
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int ans = -1e9;
for(int i=1;i<=1000;i++){
ans=max(ans,cal(i,b)-cal(i,a));
}
cout<<ans<<endl;
}

第四题

暴力骗分,没有ac,tle了

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
34
35
36
#include<bits/stdc++.h>
using namespace std;

int main(){
int n;
cin>>n;
string s;
cin>>s;
vector<vector<int>>v(26,vector<int>(n));

v[s[0]-'a'][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<26;j++){
v[j][i]=v[j][i-1];
}
v[s[i]-'a'][i]++;
}

int ans = 0;
for(int i=0;i<s.size();i++){
for(int j=i;j<s.size();j++){
for(int ch=0;ch<26;ch++){
if(i==0){
if(v[ch][j]>=(j+1+1)/2){
ans++;
}
} else{
if(v[ch][j]-v[ch][i-1]>=(j-i+1+1+1)/2){
ans++;
}
}
}
}
}
cout<<ans<<endl;
}

第五题

没时间看。。。菜哭了

感谢您的阅读。 🙏 关于转载请看这里