滴滴笔试

时间：2022/9/4 19:00~20:40 20 道选择题 两道编程题 第一题：n 个桃子，常数 k，第 i 个重量为 \(a_i\)，使一箱中最重的桃子重量不超过平均重量的 k 倍，求一箱中最多几个桃子。 通过 55%

#include<iostream>
#include<vector>
#include<algorithm> 
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector a;
    vector b;
    for (int i = 0;i < n;i++) { 
        int t; cin >> t;
        a.push_back(t);
    }
    sort(a.begin(), a.end());
    b.push_back(a[0]);
    for (int i = 1;i < n;i++) {
        b.push_back(b[i - 1]+a[i]);
    }
    int ans = 0;
    
    for(int i=0;i<n;i++){
        int num=0;
        for(int j=i+ans;j<n;j++){ 
            if ((b[j] - b[i] + a[i]) * k >= a[j] * (j - i + 1)) {
                num=j-i;
            }
        }
        ans=max(ans,num);
        if(i+ans>n){
            break;
        }
    }
    cout << ans+1 << endl;
    return 0;
}

第二题：T 次询问，T 个 L，T 个 R，T 个 t，求从 \(L_i-R_i\) 有几个数的十进制各位异或值为 \(t_i\) AC

#include<iostream>
#include<vector>
using namespace std;
vector a;
vector b;
vector c;
bool YN(int x,int flag){
    while(x){
        flag=(flag^(x%10));
        x/=10;
    }
    if(flag)
        return false;
    return true;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){ 
        int t; cin>>t;
        a.push_back(t);
    }
    for(int i=0;i<n;i++){ 
        int t; cin>>t;
        b.push_back(t);
    }
    for(int i=0;i<n;i++){ 
        int t; cin>>t;
        c.push_back(t);
    }
    for(int i=0;i<n;i++){ 
        int ans=0; 
        if(c[i]>15){
            cout<<"0 ";
            continue;
        }
        for(int j=a[i];j<=b[i];j++){
            if(YN(j,c[i]))
                ans++;
        }
        cout<<ans<<" ";
    }
    cout<<endl;
    return 0;
}