PAT~乙级~1075 链表元素分类 ~C++

墨蓝 2023-10-11 11:55 46阅读 0赞

题目描述：

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 \[0, K\] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

### 输入格式： ###

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤105)；以及正整数K (≤103)。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 `Address` 是结点地址；`Data` 是该结点保存的数据，为 \[−105,105\] 区间内的整数；`Next` 是下一结点的地址。题目保证给出的链表不为空。

### 输出格式： ###

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

### 输入样例： ###

00100 9 10
    23333 10 27777
    00000 0 99999
    00100 18 12309
    68237 -6 23333
    33218 -4 00000
    48652 -2 -1
    99999 5 68237
    27777 11 48652
    12309 7 33218

### 输出样例： ###

33218 -4 68237
    68237 -6 48652
    48652 -2 12309
    12309 7 00000
    00000 0 99999
    99999 5 23333
    23333 10 00100
    00100 18 27777
    27777 11 -1

\----------------------------------------------------------答题区----------------------------------------------------------

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <string>
    #include <unordered_map>
    #include <vector>
    using namespace std;
    struct node{ 
        string pre;
        int no;
    };
    int main(){
        string pre_;
        int num,k;
        cin>>pre_>>num>>k;
        node link[num];
        unordered_map <string,int> pre_no;
        unordered_map <string,string>pre_back;
        for(int i=0;i<num;i++){
            string pre_temp,back_temp;
            int q;
            cin>>pre_temp>>q>>back_temp;
            pre_no[pre_temp]=q;
            pre_back[pre_temp]=back_temp;
        }
        vector <node> v;
        for(int i=0;i<num &&pre_!="-1";i++){
            v.push_back({pre_,pre_no[pre_]});
            pre_=pre_back[pre_];
        }
        vector <node> ans;
        for(int i=0;i<v.size();i++){
            if(v[i].no<0){
                ans.push_back(v[i]);
            }
        }
        for(int i=0;i<v.size();i++){
            if(v[i].no>=0 && v[i].no<=k){
            ans.push_back(v[i]);
            }
        }
        for(int i=0;i<v.size();i++){
            if(v[i].no>k){
                ans.push_back(v[i]);
            }
        }
        for(int i=0;i<ans.size();i++){
            if(i==0){
            printf("%s %d ",ans[i].pre.c_str(),ans[i].no);
            // cout<<ans[i].pre<<" "<<ans[i].no<<" ";
            }
            else{
            printf("%s\n",ans[i].pre.c_str());
            // cout<<ans[i].pre<<endl;
            printf("%s %d ",ans[i].pre.c_str(),ans[i].no);
            // cout<<ans[i].pre<<" "<<ans[i].no<<" ";
            }
            if(i==ans.size()-1){
                printf("-1");
                // cout<<-1;
            }
        }
        return 0;
    }

已经考完了乙级，虽然结果不是很理想，大家可以看一下我的经验贴https://blog.csdn.net/qq\_40612211/article/details/100973477。

维护了一个PAT测试点问题的共享文档，欢迎大家把遇到的问题写在上面。

一起写文档：https://yiqixie.com/d/home/fcACe6xZ2aroPxFQrQZ05Cw32  
github链接：https://github.com/Makerdd/PAT-yiji