当前位置：首页 > article >正文

lanqiaoOJ 3255：重新排队 ← STL list 单链表

article 2024/11/2 7:18:01

【题目来源】
https://www.lanqiao.cn/problems/3255/learning/

【题目描述】
给定按从小到大的顺序排列的数字 1 到 n，随后对它们进行 m 次操作，每次将一个数字 x 移动到数字 y 之前或之后。请输出完成这 m 次操作后它们的顺序。

【输入格式】
第一行为两个数字 n, m，表示初始状态为 1 到 n 的从小到大排列，后续有 m 次操作。
第二行到第 m+1 行，每行三个数 x, y, z。当 z=0 时，将 x 移动到 y 之后；当 z=1 时，将 x 移动到 y 之前。

【输出格式】
一行，n 个数字，中间用空格隔开，表示 m 次操作完成后的排列顺序。

【输入样例】
5 3
3 1 0
5 2 1
2 1 1

【输出样例】
2 1 3 5 4

【算法分析】
★ 在大多数情况下，可以直接使用 C++ 中的 STL list，而不需手写链表。通过这种方式完成的代码通常更简洁。本例代码中将会使用 list<int>::iterator it=find(ls.begin(),ls.end(),y); 得到 y 的位置。

★ STL list：https://cplusplus.com/reference/list/
（1）size()：Returns the number of elements in the list container.
（2）empty()：Returns whether the list container is empty (i.e. whether its size is 0).
（3）push_front()：Inserts a new element at the beginning of the list, right before its current first element.
（4）push_back()：Adds a new element at the end of the list container, after its current last element.
（5）pop_front()：Removes the first element in the list container, effectively reducing its size by one.
（6）pop_back()：Removes the last element in the list container, effectively reducing the container size by one.
（7）front()：Returns a reference to the first element in the list container.
（8）back()：Returns a reference to the last element in the list container.
（9）reverse()：Reverses the order of the elements in the list container.
（10）insert()：The container is extended by inserting new elements before the element at the specified position.
（11）erase()：Removes from the list container either a single element (position) or a range of elements ([first,last)).
（12）unique()：Notice that an element is only removed from the list container if it compares equal to the element immediately preceding it. Thus, this function is especially useful for sorted lists.

【算法代码】

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;

    list<int> ls;
    for(int i=1; i<=n; i++) {
        ls.push_back(i);
    }

    while(m--) {
        int x,y,z;
        cin>>x>>y>>z;
        ls.remove(x);
        list<int>::iterator it=find(ls.begin(),ls.end(),y);
        if(z==0) ls.insert(++it,x);
        if(z==1) ls.insert(it,x);
    }

    for(auto i:ls) cout<<i<<" ";
    cout<<endl;

    return 0;
}

/*
in:
5 3
3 1 0
5 2 1
2 1 1

out:
2 1 3 5 4
*/

【参考文献】
https://blog.csdn.net/mc10141222/article/details/123674677
https://cplusplus.com/reference/list/list/

查看全文

http://www.kler.cn/a/375516.html