title: PAT1133
date: 2021-01-22 20:03:07
tags: PAT

1133

题目：

链表分割成三部分，一部分比零小的，一部分比一个特定值小的，一部分比特定值大的，且分完后顺序不能改变

范围:

最多 10^5 个节点

分析:

1. 链表乱序输入
2. 坑 不一定链表包含所有节点所以链表存储要注意提前退出，否则可能报段错误
3. 坑 比较方式是小于和大于等于

解法:

• 顺序存储
• 扫描三次，依次挑出来添加入队列
• 输出队列元素和他们的地址，以及下一个的地址

代码:

#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std; 

struct val
{
    /* data */
    int val; 
    string add; 
    string to; 
};


val negative[100005], less_line[100005], better_line[100005]; 
map<string, val> list; 
val num[100005];
vector<val> num_range;  


int main(){
    freopen("./1133_in","r",stdin); //提交时把这行注释掉就行
    string a, c, start;
    int b, n, line; 
    
    int j = 0, k = 0, l = 0, count = 0; //j: neg, k: less than k, l: better than line
    cin>>start>>n>>line; 
    for(int i = 0; i < n; i++){
        cin>>a>>b>>c; 
        val tmp_val = {b, a, c}; 
        list[a] = tmp_val; 
    }
    for(int i = 0; i < n; i++){
        num[i] = list[start]; 
        start = list[start].to;
        if(start == "-1") {
            count = i+1; 
            break; 
        }
    }
    for(int i = 0 ; i < count; i++){
        if(num[i].val < 0){
            negative[j] = num[i]; 
            j++;            
        }
        else if(num[i].val <= line){
            less_line[k] = num[i];
            k++; 
        }
        else{
            better_line[l] = num[i]; 
            l++;
        }
    }
    for(int i = 0; i < count; i++){
        if(i < j){
            num[i] = negative[i]; 
        }
        else if(i < j + k){
            num[i] = less_line[i - j]; 
        }
        else {
            num[i] = better_line[i - j - k]; 
        }
    }
    for(int i = 0; i < count; i++){
        // cout<<num[i].add<<" "<<num[i].val<<" "; 
        printf("%s %d ", num[i].add.c_str(), num[i].val); 
        if(i == count - 1) printf("-1\n"); 
        else printf("%s\n", num[i+1].add.c_str()); 
    }

    // for(int i = 0; i < n; i++){
    //     if(num[i].val < 0) num_range.push_back(num[i]);
    // }
    // for(int i = 0; i < n; i++){
    //     if(num[i].val >= 0 && num[i].val <= line) num_range.push_back(num[i]);
    // }
    // for(int i = 0; i < n; i++){
    //     if(num[i].val > line) num_range.push_back(num[i]);
    // }
    // for(int i = 0; i < n; i++){
    //     if(i == n - 1) cout<<num_range[i].add<<" "<<num_range[i].val<<" "<<"-1"<<endl; 
    //     else cout<<num_range[i].add<<" "<<num_range[i].val<<" "<<num_range[i+1].add<<endl; 
    // }
    
}