题解 | #Tk的构造数组#

排序题。

1. 把数组 a 按照 a[i] * i 的大小进行升序排序。
2. 把数组 b 按照 b[i] 的大小进行升序排序。
3. 此时从 1 ~ n, 保证所有 a[i] * b[i] * i 的总和是最大的。
4. 题目仅要求把数组 b 重新排序，故开一个空数组 c, 从 1 ~ n, 让 c[a[i].se] = b[i]。其中 a[i].se 指的是 a[i] 升序排序前最初的下标。
5. 存完后的数组 c 就等价于数组 b 对应数组 a 最初状态下排序的结果，即 b[i] 的最大值 对应 a[i] * i 的最大值，b[i] 的最小值 对应 a[i] * i 的最小值，输出即可。

附：a[i] * i 可能会超出 int 范围，运算过程中需要 * 1LL 临时转化为 long long 。

#include <iostream>
#include <algorithm>
#include <utility>
#define fi first
#define se second

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 2e5 + 10;

pii a[N];
int b[N], c[N];

bool cmp(pii& x, pii& y) {
	return 1LL * x.fi * x.se < 1LL * y.fi * y.se;
}

int main() {
	int n; cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].fi;
		a[i].se = i;
	}
	for(int i = 1; i <= n; i++) cin >> b[i];
	
	sort(a + 1, a + n + 1, cmp);
	sort(b + 1, b + n + 1);
	
	for(int i = 1; i <= n; i++) c[a[i].se] = b[i];
	
	for(int i = 1; i <= n; i++) cout << c[i] << " ";
	
	return 0;
}