|
|
发表于 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 |
|
楼主
