CF2040C Ordered Permutations
Tag：注意力
题目描述
给定一个长度为 \(n\) 的整数排列 \(p_1, p_2, \ldots, p_n\)，其中包含从 \(1\) 到 \(n\) 的所有整数。我们定义一个如下的和式：
\[S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l+1}, \ldots, p_r)\]
我们希望找出所有能使 \(S(p)\) 最大的排列，并从中按字典序选择第 \(k\) 个。如果这样的排列数量少于 \(k\)，则输出 -1。
数据说明：
\(1 \le n \le 2 \cdot 10^5\); \(1 \le k \le 10^{12}\)
分析
首先考虑一下 \(S\) 的最大值， 可以发现我们把 \(1\) 到 \(n\) 的所有数字按顺序排列时可以得到最大值。
思考一种情况，如果我们已经从大到小构造好了一部分，那么下一个小 \(1\) 的数字应该放在那里。 如果我们把下一个数字放在中间，那么很显然，之前排列好的部分中有很多区间贡献会被减少， 所以我们应该把下一个数字放在前面或者后边。 因此我们对 \(k\) 进行二进制拆分决定放在前面还是后面即可。
代码实现
void NeverSayNever() {
int n,k;
cin >> n >> k;
k--;
deque<int> dq;
dq.push_back(n);
int cur = n - 1;
while (k) {
if (k & 1) dq.push_back(cur);
else dq.push_front(cur);
cur--;
k >>= 1;
}
if (cur < 0) {
cout << -1 << endl;
return;
}
for (int i = cur; i > 0 ; i--) {
dq.push_front(i);
}
for (auto &x: dq) {
cout << x << ' ';
}
cout << endl;
}
日志
本页面创建于 2024/02/16 14:59