区块反转
题目 区块反转
思路分析
思路如 翻转单词顺序
先直接用下标做地址模拟存入
然后利用所有值都是由addr索引到的特性
可以直接对addr进行几次翻转操作
使得后面的addr顺序存放在q中
q[i]为当前地址 q[i+1]为下一个地址
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int e[N],ne[N];
int q[N];
int h,n,m;
int main()
{
cin>>h>>n>>m;
while(n--){
int addr,data,nextaddr;
cin>>addr>>data>>nextaddr;
e[addr]=data;
ne[addr]=nextaddr;//在addr下标处 对应存放数据和指针（地址）
}
//把所有的地址取出来进行操作 因为数据都是靠地址索引的 所以只需要对地址操作即可
int cnt=0;
for(int i=h;i!=-1;i=ne[i])
q[cnt++]=i;
reverse(q,q+cnt);
for(int i=cnt-1;i>=0;i-=m){
reverse(q+max(0,i-m+1),q+i+1);
}
for(int i=0;i<cnt;i++){
//经过几次翻转后 现在的对应关系在q中 可以用q中存的addr索引到e里的值
int addr=q[i],nextaddr=q[i+1];
printf("%05d %d ",addr,e[addr]);
if(i==cnt-1)
cout<<"-1"<<endl;
else
printf("%05d\n",nextaddr);
}
return 0;
}
💬 评论