9.4滴滴笔试题解 82% 100%

第一题过了82%，第二题过了100%

第一题每次删最大的数才能维持条件，就是不知道为啥一直卡在82%

第二题哈希+二分直接过，100%

第一题桃子装箱

n个桃子，每个重ai，尽可能多的装入一个箱子，要求箱子内最终的桃子重量不能超过平均重量的k倍，问最多能装多少个桃子？

输入：

第一行n和k。

第二行n个数，对应每个桃子的重量。

输出：最多能装的数量

例子：

输入：

5 2

3 10 5 4 2

输出：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    double k;
    while (cin>>n>>k)
    {
        vector<long long> nums(n, 0);
        long long  sum = 0;
        double avg;
        priority_queue<long long> q;
        for (long long i = 0; i < n; ++i){
            cin>>nums[i];
            sum += nums[i];
            q.push(nums[i]);
        }    
        while (double(n / k) * q.top() > double(sum))
        {
            sum -= q.top();
            n--;
            q.pop();
        }
        cout<<n<<endl;
    }
    return 0;
}

第二题老张的美术课

对于每个非负整数都有一个美丽值，美丽值定义为这个数十进制下每个数位的异或和，如123的美丽值是1^2^3=0。问对于一个闭区间[L, R]中所有的整数，美丽值恰好为t的数有多少个？

输入：

第一行一个正整数T，代表T个询问

第二行T个非负整数，Li

第三行T个非负整数，Ri

第四行T个非负整数，ti

输出：

每个询问输出一个整数，每个输出用空格隔开

例子：

输入：

0 1

0 10

0 1

输出：

1 2

#include <bits/stdc++.h>
using namespace std;
int get_xor(long long x)
{
    int res = 0;
    while (x)
    {
        res ^= (x % 10);
        x /= 10;
    }
    return res;
}
int main()
{
    unordered_map<long long, vector<long long>> map;
    for (long long i = 0, r; i <= 70000; ++i)
    {
        r = get_xor(i);
        map[r].push_back(i);
    }
    int n;
    while (cin >> n)
    {
        vector<long long> L(n, 0), R(n, 0), Q(n, 0);
        for (int i = 0; i < n; ++i) cin >> L[i];
        for (int i = 0; i < n; ++i) cin >> R[i];
        for (int i = 0; i < n; ++i)
        {
            cin >> Q[i];
            int lindex = lower_bound(map[Q[i]].begin(), map[Q[i]].end(), L[i]) - map[Q[i]].begin();
            int rindex = lower_bound(map[Q[i]].begin(), map[Q[i]].end(), R[i]) - map[Q[i]].begin();
            cout<<rindex - lindex + 1<<" ";
        }
        cout<<endl;
    }   
    return 0;
}

#滴滴笔试##滴滴23秋招笔试有点儿难啊#