【PAT甲级】1052 Linked List Sorting (25 分)
2024-10-08 13:48:50
题意:
输入一个正整数N(<=100000),和一个链表的头结点地址。接着输入N行,每行包括一个结点的地址,结点存放的值(-1e5~1e5),指向下一个结点的地址。地址由五位包含前导零的正整数组成。以头结点地址开始的这条链表以值排序后得到的链表的长度和头结点,接着以升序按行输出每个结点的地址和值以及指向下一个结点的地址。
trick:
题干说的postive N可是数据点4出现了N==0的数据,有些不解如果N==0应该包含的话不应该用nonnegative N吗。。。
数据点1包含有些结点并非在头结点所在的这条链表上。(题干说给一条联通的链表,实际可能有些点并不在该链表上)
通过一些题目可见,有些trick不会明显的在题干中给出,题干只保证一些一定不会发生的情况,还有一些边界条件以及可能出现的问题需要自行多加考虑。。。。。
AAAAAccepted code:
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
pair<int,int>pr[];
pair<int,int>ans[];
int main(){
int n;
int add;
scanf("%d%d",&n,&add);
for(int i=;i<=n;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
pr[x]={y,z};
}
int cnt=;
while(){
if(pr[add].second){
ans[++cnt].first=pr[add].first;
ans[cnt].second=add;
add=pr[add].second;
}
else
break;
}
if(!cnt)
printf("0 -1");
else{
sort(ans+,ans++cnt);
printf("%d %05d\n",cnt,ans[].second);
for(int i=;i<=cnt;++i){
printf("%05d %d ",ans[i].second,ans[i].first);
if(i!=cnt)
printf("%05d\n",ans[i+].second);
else
printf("-1");
}
}
return ;
}
最新文章
- 利用 iframe解决ajax的跨域问题
- java自定义异常(Exception、throws、try-catch)
- JavaScript使用自定义事件实现简单的模块化开发
- OpenCv for Android
- IMX6下移植WKxxx驱动
- Matlab实现Hough变换检測图像中的直线
- linux配置使用外部smtp发送邮件
- PHP中递归最详解释.
- 33. Springboot 系列 原生方式引入Redis,非RedisTemplate
- vue的data的数据进行指定赋值,用于筛选条件的清空,或者管理系统添加成功后给部分数据赋值为空
- C++ Exception机制
- VMware安装步骤既常见问题
- ie 浏览器缓存问题
- Kali系列之aircrack-ng wifi密码穷举
- Windows下war包部署到Linux下Tomcat出现的问题
- 标准JAVA MD5方法
- MyEclipse:详细使用教程
- js 取值 getElementsByTagName,getElementsByName
- C++练习 | 递归判断二叉树是否同构
- CodeForces - 1004B