美团第二次笔试，记录

第一题，栈模拟

void first(){
    int t;
    cin>>t;

    while(t>0){
        int n;
        cin>>n;
        vector<int> nums(n);
        vector<int> target(n);
        
        for(int i=0;i<n;i++){
            cin>>nums[i];
        }
        stack<int> sta;

        sta.push(nums[0]);

        for(int i=0;i<n;i++){
            cin>>target[i];
        }
        int temp=1;
        for(int i=0;i<n;i++){
            if(sta.empty()&&temp<n){
                sta.push(nums[temp++]);
            }
            while(target[i]!=sta.top() && temp<n){
                sta.push(nums[temp++]);
            }

            if(temp==n && sta.top()!=target[i]){
                cout<<"No"<<endl;
                break;
            }
            else{
                sta.pop();
            }
        }
        if(sta.empty()){
            cout<<"Yes"<<endl;
        }
        t--;
    }
}

第二题 简单dp;

void second(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<int> dp(n,0);
    if(n==1){ cout<<nums[0]<<endl;return;}
    if(n==2){ cout<<max(nums[0],nums[1])<<endl;return;}
    if(n==3){ cout<<max(nums[0],max(nums[1],nums[2]))<<endl;return;}
    
    dp[0]=nums[0];
    dp[1]=max(nums[1],dp[0]);
    dp[2]=max(dp[1],nums[2]);

    for(int i=3;i<n;i++){
        dp[i]=max(dp[i-3]+nums[i],dp[i-1]);
    }
    cout<<dp[n-1]<<endl;
}

第三题

前面直接写，82%，加上前缀和，没变化，加上二分查找，才过，二分查找很重要

void third(){

    int n,m;
    cin>>n>>m;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<long> bags(m);
    for(int i=0;i<m;i++){
        cin>>bags[i];
    }

    //sort(nums.begin(),nums.end());

    vector<long> prefix(n);
    prefix[0]=nums[0]*nums[0];
    for(int i=1;i<n;i++){
        prefix[i]=prefix[i-1]+nums[i]*nums[i];
    }
    int flag=0;
    for(int i=0;i<m;i++){
        long bag=bags[i];
        int left =0,right=n-1;
        bool ttt=false;
        while(left<right){
            int mid = left+(right-left)/2;
            if(prefix[mid]==bag){
                flag=mid;
                ttt=true;
                break;
            }
            else if(prefix[mid]>bag){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        if(!ttt){
            if(bag>=prefix[left]){
                flag=left;
            }
            else if(bag>=prefix[right]){
                flag=right;
            }
            else{
                flag=right-1;
            }
        }
        
        cout<<flag+1;
        if(i<m-1){
            cout<<" ";
        }
    }

}

第四题

用map模拟

void four(){
    string str;
    cin>>str;
    int n;
    cin>>n;
    vector<string> query(n);
    for(int i=0;i<n;i++){
        cin>>query[i];
    }

    string temp="";
    string key="";
    unordered_map<string,string> map;
    int len = str.size();
    for(int i=0;i<len;i++){
        if(str[i]=='='){
            key=temp;
            temp="";
        }
        else if(str[i]==';'){
            map[key]=temp;
            temp="";
        }
        else{
            temp+=str[i];
        }
    }
    for(int i=0;i<n;i++){
        if(map.find(query[i])==map.end()){
            cout<<"EMPTY"<<endl;
        }
        else{
            cout<<map[query[i]]<<endl;
        }
    }
}

第五题 压轴的动态规划，又有破坏次数，还要买和不买

void fifth(){
    int n,k;
    cin>>n>>k;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    
    vector<vector<vector<int>>> dp(n,vector<vector<int>>(k+1,vector<int>(2,0)));
    dp[0][0][1]=nums[0];

    for(int i=1;i<n;i++){
        dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1]);
        dp[i][0][1]=dp[i-1][0][0]+nums[i];
        for(int j=1;j<=k;j++){
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
            dp[i][j][1]=max(dp[i-1][j-1][1],dp[i-1][j][0])+nums[i];
        }
    }

    cout<<max(dp[n-1][k][0],dp[n-1][k][1])<<endl;

}