美团笔试2

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.7k 阅读时长 ≈ 3 分钟

备注

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

第一题

输入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;
}

第五题

没时间看。。。菜哭了