美团8月13日笔试（C++）

AK了，但是答案可能不是最优，如果有更好的答案欢迎讨论

第一题

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int n,t;
    cin>>n>>t;
    vector<int>vec(n);
    for(int i=0;i<n;++i){
        cin>>vec[i];
    }
    sort(vec.begin(),vec.end());
    int res = 0;
    int cur = t;
    for(int i=0;i<n;++i){
        if(vec[i]<cur){
            ++res;
        }
        else{
            cur+=t;
        }
    }
    cout<<res<<endl;
    return 0;
}

第二题

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<bool>>grid(n,vector<bool>(m,0));
    string s;
    cin>>s;
    int clean = 1;
    int x = 0, y=0;
    grid[0][0]=true;
    int i=0;
    for(;i<k;++i){
        switch (s[i])
        {
        case 'W':
            --x;
            break;
        case 'A':
            --y;
            break;
        case 'S':
            ++x;
            break;
        case 'D':
            ++y;
            break;
        default:
            break;
        }
        if(!grid[x][y]){
            ++clean;
            grid[x][y]=true;
        }
        if(clean==m*n){
            break;
        }
    }
    if(i==k){
        cout<<"No"<<endl;
        cout<<m*n-clean;
    }
    else{
        cout<<"Yes"<<endl;
        cout<<i+1<<endl;
    }
    return 0;
}

第三题

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0;i<n;++i){
        cin>>vec[i];
    }
    vector<int>result(n,-1);
    int cur = 0;
    for(int i=0;i<n;++i){
        int num=0;
        while(true){
            if(result[cur]==-1&&num==2){
                break;
            }
            if(result[cur]==-1){
                ++num;
            }
            cur = (cur+1)%n;
        }
        result[cur]=vec[i];
    }
    for(int i:result){
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

第四题

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>vec(n);
    unordered_map<int,int>mp;
    for(int i=0;i<n;++i){
        cin>>vec[i];
    }
    long long res=0;
    for(int j=0;j<n;++j){
        for(int k=j+1;k<n;++k){
            int t = 3*vec[j]-vec[k];
            if(mp.count(t)){
                res+=mp[t];
            }
        }
        ++mp[vec[j]];
    }
    cout<<res<<endl;
    return 0;
}

第五题

#include<iostream>
#include<vector>

using namespace std;

vector<int>vec;
int n;
int res;

void dfs(int node,int cur){
    int left = node*2;
    int right = node*2+1;
    cur+=vec[node];
    if(left>n){
        res = max(res,cur);
    }
    if(left<=n)
        dfs(left,cur);
    if(right<=n)
        dfs(right,cur);
}

int main(){
    cin>>n;
    vec.resize(n+1);
    for(int i=1;i<=n;++i){
        cin>>vec[i];
    }
    res = 0;
    dfs(1,0);
    cout<<res<<endl;
    return 0;
}