拼多多笔试代码 2023.10.08

第一题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1e5+5;
int k[N],l[N];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>k[i];
    for(int i=0;i<n;i++)cin>>l[i];
    sort(k,k+n);
    sort(l,l+n);
    int le,ri;
    le=ri=0;
    int ans=0;
    while(le<n&&ri<n){
        if(k[le]>l[ri]){
            le++;
            ri++;
            ans++;
        }else{
            le++;
        }
    }
    cout<<ans<<endl;
}

第二题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1005;
ll w[N],sum[N];
int main(){
    // cout<<256.0/(988+100+132)<<endl;
    int t;cin>>t;
    while(t--){
        memset(w,0,sizeof(w));
        memset(sum,0,sizeof(sum));
        int n,k;cin>>n>>k;
        double use_temp=k*0.01;
        for(int i=0;i<n;i++){
            cin>>w[i];
            if(i==0)sum[i]=w[i];
            else sum[i]=sum[i-1]+w[i];
        }
        ll ans=0;
        for(int i=1;i<n;i++){
            sum[i-1]+=ans;
            double temp=w[i]*1.0/(sum[i-1]*1.0);
            // cout<<temp<<endl;
            if(temp<use_temp){
                continue;
            }else{
                double kk=(w[i]*1.0)/use_temp;
                int x=kk;
                double y=kk-x;
                if(y>0){
                    x++;
                }
                ans+=(x-sum[i-1]);
            }
        }
        cout<<ans<<endl;
    }
}

第三题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define ll long long
using namespace std;
queue<string>q,q2,q3,q4,q5,q6;
int main(){
    int t;cin>>t;
    while(t--){
        int m;
        string s;
        ll ans=0;
        cin>>m>>s;
        while(!q.empty())q.pop();
        while(!q2.empty())q2.pop();
        while(!q3.empty())q3.pop();
        while(!q4.empty())q4.pop();
        while(!q5.empty())q5.pop();
        while(!q6.empty())q6.pop();
        q.push(s);
        while(!q.empty()){
            string temp=q.front();q.pop();
            string son="";
            for(int i=0;i<temp.length();){
                if(i+2<temp.length()){
                    if(temp[i]=='P'&&temp[i+1]=='D'&&temp[i+2]=='D'){
                        ans++;
                        if(son!=""){
                            q2.push(son);
                        }
                        son="";
                        i+=3;
                    }else{
                        son+=temp[i];
                        i++;
                    }
                }else{
                    son+=temp[i];
                    i++;
                }
            }
            if(son!=""){
                q2.push(son);
            }
        }


        // while(!q2.empty()){
        //     if(m<=0)break;
        //     string temp=q2.front();q2.pop();
        //     string son="";
        //     for(int i=0;i<temp.length();){
        //         if(i+2<temp.length()){
        //             if(temp[i]=='P'&&temp[i+2]=='D'){
        //                 if(m<=0)break;
        //                 else{
        //                     ans++;
        //                     m--;
        //                 }
        //                 if(son!=""){
        //                     q3.push(son);
        //                 }
        //                 son="";
        //                 i+=3;
        //             }else{
        //                 son+=temp[i];
        //                 i++;
        //             }
        //         }else{
        //             son+=temp[i];
        //             i++;
        //         }
        //     }
        //     if(son!=""){
        //         q3.push(son);
        //     }
        // }

        while(!q2.empty()){
            if(m<=0)break;
            string temp=q2.front();q2.pop();
            string son="";
            for(int i=0;i<temp.length();){
                if(i+1<temp.length()){
                    if((temp[i]=='P'&&temp[i+1]=='D')||(temp[i]=='D'&&temp[i+1]=='D')){
                        if(m<=0)break;
                        else{
                            ans++;
                            m--;
                        }
                        if(son!=""){
                            q4.push(son);
                        }
                        son="";
                        i+=2;
                    }else{
                        son+=temp[i];
                        i++;
                    }
                }else{
                    son+=temp[i];
                    i++;
                }
            }
            if(son!=""){
                q4.push(son);
            }
        }

        while(!q4.empty()){
            if(m<=1)break;
            string temp=q4.front();q4.pop();
            string son="";
            for(int i=0;i<temp.length();){
                if(temp[i]=='P'||temp[i]=='D'){
                    if(m<=1)break;
                    else{
                        ans++;
                        m-=2;
                    }
                    if(son!=""){
                        q5.push(son);
                    }
                    son="";
                    i++;
                }else{
                    son+=temp[i];
                    i++;
                }
            }
            if(son!=""){
                q5.push(son);
            }
        }
        ans+=(m/3);
        cout<<ans<<endl;
    }
}

第四题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define ll long long
using namespace std;
const int N = 1e5+5;
ll k[N];
ll val[N];
ll sum;
ll n,t;
void dfs(int pos,ll weigh,int step){
    val[pos]=min(val[pos],weigh);
    for(int i=0;i<=step;i++){
        if(k[1+i+pos]+val[pos]>t)continue;
        if(1+i+pos>n)continue;
        if(k[1+i+pos]+val[pos]<val[1+i+pos])
        dfs(1+i+pos,k[1+i+pos]+val[pos],step);
    }
}
ll solve(int step){
    for(int i=0;i<=step;i++){
        // cout<<1+i<<' '<<k[1+i]<<' '<<step<<endl;
        if(k[1+i]>t)continue;
        if(1+i>n)continue;
        dfs(1+i,k[1+i],step);
    }
    ll target_val=sum+1;
    // cout<<step<<' ';
    for(int i=n;i>=n-step;i--){
        // cout<<val[i]<<' ';
        target_val=min(target_val,val[i]);
    }
    // cout<<endl;
    // cout<<"adsa "<<step<<' '<<target_val<<endl;
    return target_val;
}
int erfen(int le,int ri){
    int mid=(le+ri)>>1;
    while(le<ri){
        for(int i=0;i<=n;i++){
            val[i]=sum+1;
        }
        // cout<<mid<<endl;
        // cout<<solve(mid)<<' ';
        if(solve(mid)<=t){
            ri=mid;
        }else{
            le=mid+1;
        }
        // cout<<le<<' '<<ri<<endl;
        mid=(le+ri)>>1;
    }
    if(solve(mid)>t){
        le=le-1;
    }
    return le;
}
int main(){
    int T;cin>>T;
    while(T--){
        memset(k,0,sizeof(k));
        cin>>n>>t;
        sum=0;
        for(int i=1;i<=n;i++){
            cin>>k[i];
            sum+=k[i];
        }
        if(sum<=t){
            cout<<0<<endl;
        }else{
            int ans=erfen(1,n);
            cout<<ans<<endl;
        }
    }
}