Card Deck CodeForces - 1492B
你有一副 n 张牌，你想把它重新排序为一副新的。
每张卡都有一个介于 1 和 n 之间的值，该值等于 pi。所有 pi 两两不同。
牌组中的牌是从下到上编号的，即 p1 代表最下面的牌，pn 代表最上面的牌。
在每个步骤中，您选择一些整数 k>0，从原始牌组中取出顶部的 k 张牌，并将它们按现在的顺序放在新牌组的顶部。您可以执行此操作，直到原始数据组为空。
让我们将甲板的顺序定义为 \(\sum\limits_{i=1}^{n}{n^{n-i}* p_i}\)
给定原始数据组，使用上面的操作以最大可能的顺序输出数据组。
Input
第一行包含一个整数 t（1≤t≤1000）-测试用例的数量。
每个测试用例的第一行包含单个整数 n（1≤n≤1e5)-甲板的尺寸。
第二行包含 n 个整数 pi（\(1≤pi≤n; p_i \neq pj, i \neq j\)）-牌组中卡片从下到上的值。
保证所有测试用例中 n 的总和不超过1e5。
Output
对于每个测试用例，打印具有最大可能顺序的数据组。
从下到上打印卡片组中卡片的值。
如果有多个答案，请打印其中任何一个。
Sample Input
4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1
Sample Output
4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1
样例解释
在第一个测试案例中，最佳策略之一是下一个：
- 从p的顶部取1张牌，移动到p'：p变为[1,2,3]，p'变为[4]；
- 从p顶部取1张牌：p变为[1,2]，p'变为[4,3]；
- 从p顶部取1张牌：p变为[1]，p'变为[4,3,2]；
- 从p顶部取1张牌：p变空，p'变为[4,3,2,1]。
结果，p'的顺序等于 \(4^3* 4+4^2\cdot 3+4^1* 2+4^0* 1=256+48+8+1=313\)。
在第二个测试案例中，最佳策略之一是：
- 从p的顶部取4张牌，移动到p'：p变成[1]，p'变成[5,2,4,3]；
- 从p顶部取1张牌，移动到p'：p变空，p'变为[5,2,4,3,1]；
结果，p'的顺序等于 \(5^4*5+5^3* 2+5^2* 4+5^1* 3+5^0*1=3125+250+100+15+1=3491\)
分析
- \(\sum\limits_{i=1}^{n}{n^{n-i}* p_i}\) 这个公式不就是一个 n 进制数的值嘛
- 也就是按照要求组合出一个新数，且该数的 n 进制最大
- 考虑如何使得进制数最大，必然是最大元素的权值尽可能大，即 {p1,p2,...,pn} 按序组成的数尽可能大。
- 发现每次就是选择最大及其上方元素作为一个整体组成新的序列。
- 所以问题其实转化为找最大值，但是由于后续元素是和前方最值绑定在一起的
- 考虑预处理前方 a[1..i] 的最大值 mx[i]，之后逆序配对 (a[i]==mx[i]) 即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
int t,n,a[N],mx[N];
int main() {
// freopen("data.in", "r", stdin);
cin>>t;
while(t--){
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) mx[i]=max(mx[i-1], a[i]);
for(int i=n,r=n; i>=1; i--){
if(a[i]==mx[i]){
for(int j=i; j<=r; j++) cout<<a[j]<<" ";
r=i-1;
}
}
cout<<endl;
}
return 0;
}