9.4滴滴笔试题解 82% 100%
第一题过了82%，第二题过了100%
第一题每次删最大的数才能维持条件，就是不知道为啥一直卡在82%
第二题哈希+二分直接过，100%
第一题桃子装箱
n个桃子，每个重ai，尽可能多的装入一个箱子，要求箱子内最终的桃子重量不能超过平均重量的k倍，问最多能装多少个桃子？
输入：
第一行n和k。
第二行n个数，对应每个桃子的重量。
输出：最多能装的数量
例子：
输入：
5 2
3 10 5 4 2
输出：
4
#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
输出：
每个询问输出一个整数，每个输出用空格隔开
例子：
输入：
2
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;
} 
