士兵队列训练问题（链表）

男娘i 2023-07-16 03:51 6阅读 0赞

### 士兵队列训练问题 ###

*   *  介绍list实战经验
     *  题目：
     *  我的代码：

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

## 介绍list实战经验 ##

List容器是一种实现了双向链表的数据结构，它的每个节点都含有前驱元素指针域、数据域、后继元素指针域。不同于数组这样的线性表，由于list元素的前驱和后继都是靠指针来链接，因此在链表的任意位置进行元素的插入、删除和查找操作速度是较快的。由于list对象的结点并不要求在一段连续的内存中，所以对于迭代器，只能通过“++”或者“–”的操作，不能对其进行+N或者-N的操作。

一）创建list对象：

> （1）创建没有任何元素的list对象：list l;
> 
> （2）创建具有n个元素的list对象：list l(10); //创建具有10个整形元素的list对象l 。

（二）插入元素：

> （1）使用push\_back()方法从尾部插入元素，链表自动扩张；
> 
> （2）使用push\_front()方法从头部插入元素，链表自动扩张；
> 
> （3）使用insert()方法向迭代器位置插入新元素，链表自动扩张。

（三）遍历元素：

> （1）前向遍历：以前向迭代器的方式遍历；
> 
> （2）反向遍历：使用反向迭代器进行遍历。

（四）删除元素：

> （1）remove(元素值)，删除链表中的元素，值相同的元素都会被删除；
> 
> （2）pop\_front()删除链表首元素；
> 
> （3）pop\_back()删除链表尾元素；
> 
> （4）erase()删除迭代器位置的元素；
> 
> （5）clear()清空链表容器。

（五）查找元素：**需要添加\#include**

> find(迭代器1，迭代器2，元素)，函数返回一个迭代器值，若该值被找到则返回该值所在的迭代器值，若没有找到则返回end()迭代器的位置。

（六）list排序：

> 使用list的成员函数sort()实现升序排序

#include<iostream>  
    #include<list>  
    #include<algorithm>  
    using namespace std;  
      
    int main()  
    {
          
    	int i;
    	list<int> l;
    	list<int>::iterator pos;
    	list<int>::reverse_iterator pos1;
    	l.push_back(1);
    	l.push_back(2);
    	l.push_back(3);
    	l.push_back(4);
     
    	//前向遍历
    	for(pos=l.begin();pos!=l.end();pos++)
    		cout<<*pos<<" ";
    	cout<<endl;
        
    	//反向遍历
    	for(pos1=l.rbegin();pos1!=l.rend();pos1++)
    		cout<<*pos1<<" ";
    	cout<<endl;
     
        return 0;  
    } 
    输出结果：
    1 2 3 4
    4 3 2 1

lst1.assign() // 给list赋值  
lst1.front() // 返回第一个元素  
lst1.back() // 返回最后一个元素  
lst1.begin() // 返回指向第一个元素的迭代器  
lst1.end() // 返回末尾的迭代器  
lst1.insert() // 插入一个元素到list中  
lst1.erase() // 删除一个元素  
lst1.pop\_back() // 删除最有一个元素  
lst1.pop\_front() // 删除第一个元素  
lst1.clear() // 删除所有元素  
lst1.remove(const T & val) // 删除和val相等的元素  
lst1.push\_back() // 在list的末尾添加一个元素  
lst1.push\_front() // 在list的首部添加一个元素  
lst1.empty() // 判断，若list为空返回true  
lst1.max\_size() // 返回list能容纳的最大元素数量  
lst1.sort() // 给list排序(顺序)  
list.reverse() // 把list中的元素倒转  
lst1.merge(lst2) // 合并lst2到lst1，并清空lst2  
lst1.unique() // 删除所有和前一个元素相等的元素  
void splice(iterator i, list & x, iterator first, iterator last) // 在位置i前面插入链表x中的区间 \[first, last）, 并在链表x中删除该区间（链表自身和链表x可以是用一个链表，只要i不在 \[first, last) 中即可

#include <list>  // 使用 list 需要包含此头文件
    #include <algorithm>  // 使用 STL 中的算法需要包含此头文件
    #include <iostream>  
    using namespace std;
    
    class A
    {
        
    public:
    	A(int n_):n(n_){
        }
    	friend bool operator < (const A & a1, const A & a2);
    	friend bool operator == (const A & a1, const A & a2);
    	friend ostream & operator << (ostream & out, const A & a);
    private:
    	int n;
    };
    
    bool operator < (const A & a1, const A & a2){
        
    	return a1.n < a2.n;
    }
    
    bool operator == (const A & a1, const A & a2){
        
    	return a1.n == a2.n;
    }
    
    ostream & operator << (ostream & out, const A & a){
        
    	out << a.n;
    	return out;
    }
    template <class T>
    void Print(T first, T last)
    {
        
    	for(; first != last; ++first)
    		cout<<*first<<" ";
    	cout<<endl;
    }
    
    int main()
    {
        
    	A a[5] = {
        1, 3, 2, 4, 2};
    	A b[7] = {
        10, 30, 20, 30, 30, 40, 40};
    	list<A> lst1(a, a+5), lst2(b, b+7);
    	lst1.sort();    // 顺序排序
    	cout<<"1. "; Print(lst1.begin(), lst1.end());
    	lst1.remove(2);  // 删除所有和A(2)相等的元素
    	cout<<"2. "; Print(lst1.begin(), lst1.end());
    	lst2.pop_front();  // 删除第一个元素
    	cout<<"3. "; Print(lst2.begin(), lst2.end());
    	lst2.unique();  // 删除所有和前一个元素相等的元素
    	cout<<"4. "; Print(lst2.begin(), lst2.end());
    	lst2.sort();  // 顺序排序
    	lst1.merge(lst2);  // 合并 lst2 到 lst1 并清空 lst2
    	cout<<"5. "; Print(lst1.begin(), lst1.end());
    	cout<<"6. "; Print(lst2.begin(), lst2.end());  // lst2 是空的
    	lst1.reverse();  // 将 lst1 倒置
    
    	cout<<"7. "; Print(lst1.begin(), lst1.end());
    	lst2.insert(lst2.begin(), a + 1, a + 4);  // 在 lst2 中插入 3，2，4 三个元素
    	list<A>::iterator p1, p2, p3;
    	p1 = find(lst1.begin(), lst1.end(), 30);  // 查找元素
    	p2 = find(lst2.begin(), lst2.end(), 2);
    	p3 = find(lst2.begin(), lst2.end(), 4);
    	lst1.splice(p1, lst2, p2, p3);  // 将 [p2, p3) 插入p1之前，并从lst2中删除 [p2, p3)
    	cout<<"8. "; Print(lst1.begin(), lst1.end());
    	cout<<"9. "; Print(lst2.begin(), lst2.end());
    	return 0;  
    }

## 题目： ##

Total Submission(s): 20237 Accepted Submission(s): 8517

Problem Description  
某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

Input  
本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。

Output  
共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。

Sample Input  
2  
20  
40

Sample Output  
1 7 19  
1 19 37

## 我的代码： ##

这段代码是个痛苦的故事，我的赋值语句竟然写成了 == 怎么找怎么想逻辑上都好久找不到为啥出不来循环。  
简单介绍一下代码：  
定义迭代器：list::iterator it;  
题目要求最后留下的不多于3人，我就把while条件写作mylist.size()>3则每轮交替删掉2的倍数或3的倍数，遍历时如果不是其倍数，则保留它在列表里，不做任何操作，it++继续遍历下一个；如果是它的倍数，则删掉它it = mylist.erase(it);，而且删掉后我们知道it位置不变，删除一个元素后，重新指向的是相对原来的下一个节点的数据。不管it动不动，我们定义的num（暂存当前人的编码）总是不停的+1，所以实际上我们起到遍历作用的是这里的num。it起到的作用是动态处理列表中的元素。  
每轮（每行人结束后）替换2或3是通过k==2?k=3:k=2。

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        
        int t,n;
        cin>>t;
        while(t--)
        {
        
            cin>>n;
            int k = 2;
            list < int > mylist;  //定义
            list < int >::iterator  it;
            for(int i=1; i<=n; i++)
                mylist.push_back(i);  //赋值
            while(mylist.size() > 3)
            {
        
                int num = 1;
                for(it = mylist.begin(); it != mylist.end();)
                {
        
                    if(num++ % k == 0)
                        it = mylist.erase(it);
                    else
                        it++;
                }
                k == 2 ? k = 3:k = 2;
            }
            for(it = mylist.begin(); it != mylist.end(); it++)
            {
        
                if(it != mylist.begin())  //输出数据间的空格
                    cout<<" ";
                cout<<*it;  //输出it所指向的数据
            }
            cout<<endl;
        }
    
        return 0;
    }