1133. Splitting A Linked List (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1133

大概描述:

对一串数,进行粗排序,排序规则,在保持原有顺序的前提下,将负数排在前列,将大于K排在后面

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作

题目得分:

22

提交次数:

2

时间

60分钟

代码

//柳神的想法果然强
#include<cstdio>
#include<vector>
using namespace std;
const int MAXI = 100000;
vector<int> w1,w2,w3;
int m[MAXI][2];

int main(){
 int i = 0;
 int num,fir,k;
 int a,b,c;
 scanf("%d %d %d",&fir,&num,&k);
 for(i = 0;i < num;i++) {
 scanf("%d %d %d",&a,&b,&c);
 m[a][0] = b;
 m[a][1] = c;
 }
 printf("read finished\n");
int r = fir;
 while(r != -1){
 if(m[r][0] < 0){
 w1.push_back(r);
 }
 if(m[r][0] > k){
 w3.push_back(r);
 }
 if(m[r][0] <= k&& m[r][0] >= 0){
 w2.push_back(r);
 }
 r = m[r][1];
 }
 int k1 = w1.size();
 for(i = 0 ;i < k1;i++){
 if(i == 0)
 printf("%05d %d ",w1[i],m[w1[i]][0]);
 else
 printf("%05d\n%05d %d ",w1[i],w1[i],m[w1[i]][0]);
 }
 //printf("%04d\n",m[w1[i]][1]);
int k2 = w2.size();
 for(i = 0 ;i < k2;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 else
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 }
 //printf("%04d\n",m[w2[i]][1]);
 int k3 = w3.size();
 if(k3 == 0){
 printf("-1");
 }else{
 for(i = 0 ;i < k3;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 else
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 }
printf("-1");
 }
}

运行结果

22

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了

发表评论

电子邮件地址不会被公开。 必填项已用*标注