简答题
偏难
#13195
取帽子 拼题er们觉得戴帽子会令自己看上去很帅,所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅,服务员把他们的帽子收集了堆起来保管。当大家要离开的时候,…
取帽子

拼题er们觉得戴帽子会令自己看上去很帅,所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅,服务员把他们的帽子收集了堆起来保管。当大家要离开的时候,发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队,使得每个人都能按顺序顺利取到自己的帽子。
已知每顶帽子的大小都不相同,并且帽子的尺寸跟帽子主人的体重有关 —— 越重的人戴的帽子就越大。
时间限制:1000
内存限制:65536
输入
输入第一行给出一个正整数 n (≤ 104),为拼题er的人数。随后一行给出 n 个不同的帽子尺寸,为不超过 105 的正整数,顺序是从帽子堆的底部向上给出。最后一行给出 n 个不同的体重,顺序对应编号从 1 到 n 的拼题er。体重是不超过 106 的正整数。一行中的数字以空格分隔。
输出
在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
10 12 19 13 11 15 18 17 14 16 20 67 90 180 98 87 105 76 88 150 124
样例输出
3 4 8 6 10 2 1 5 9 7
提示
样例说明: 第一顶帽子的尺寸是最大的 20,所以对应第 3 个人的最大体重 180,于是第 3 个人排在最前面。 第二顶帽子的尺寸是第 6 小的 16,对应第 6 小的体重 98,是第 4 个人,于是第 4 个人下一个走。 以此类推。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
struct User {
int id;
int weight;
};
int main() {
int n;
cin >> n;
vector<int> hats(n);
for (int i = 0; i < n; ++i) {
cin >> hats[i];
}
vector<User> users(n);
for (int i = 0; i < n; ++i) {
cin >> users[i].weight;
users[i].id = i + 1;
}
// 按帽子尺寸降序排序
vector<int> sorted_hats = hats;
sort(sorted_hats.begin(), sorted_hats.end(), greater<int>());
unordered_map<int, int> hat_rank;
for (int i = 0; i < sorted_hats.size(); ++i) {
hat_rank[sorted_hats[i]] = i;
}
// 按体重降序排序用户
sort(users.begin(), users.end(), [](const User& a, const User& b) {
return a.weight > b.weight;
});
vector<int> sorted_users;
for (const User& u : users) {
sorted_users.push_back(u.id);
}
// 取出顺序是原帽子数组的逆序
vector<int> reversed_hats(hats.rbegin(), hats.rend());
vector<int> result;
for (int hat : reversed_hats) {
result.push_back(sorted_users[hat_rank[hat]]);
}
// 输出结果
for (size_t i = 0; i < result.size(); ++i) {
if (i != 0) cout << " ";
cout << result[i];
}
cout << endl;
return 0;
}</pre>
这道题暂未补解析。