|
发表于 2018-10-18 23:43:00
|
显示全部楼层
本帖最后由 118139 于 2018-10-18 23:44 编辑
下面这题今年初中奥赛普及组的最后一题, 没看明白题意,
谁来讲讲举例的 “n=5且P为1 5 4 2 3,则q为2 6 6 5 6。” 是怎么换算出来的
对于一个1到n的排列P(即1到n中每一个数在P中出现了恰好一次),令qi为第i个位置之后第一个比Pi
值更大的位置,如果不存在这样的位置则 qi=n+1。。
举例来说,如果n=5且P为1 5 4 2 3,则q为2 6 6 5 6。
下列程序读入了排列P,使用双向链表求解了答案,试补全程序。
数据范围1≤n≤10^5
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int L[N],R[N],a[N];
int main(){
cin>>n;
for(int i=1;i<=n;++i){
int x;
cin>>x;
__(1)__;
}
for(int i=1;i<=n;++i){
R=i+1;
L=i-1;
}
for(int i=1;i<=n;++i){
L[__(3)__]=L[a];
R[L[a]]=R[__(4)__];
}
for(int i=1;i<=n;++i){
cout<<__(5)__<<" ";
}
cout<<endl;
return 0;
}
答案:a[x]=i , i+1 , R[a] , a , R |
|