STL应用 —— list

STL应用 —— list

list是一个双向链表，可以在常数时间内插入和删除，不支持数组表示法和随机访问。使用list时，需要引入头文件#include。

list的专用成员函数

• merge(b)：将链表b 与调用链表合并，在合并之前，两个链表必须已经排序，合并后经过排序的链表被保存在调用链表中，b 为空。
• remove(val)：从链表中删除val的所有节点。
• splice(pos,b)：将链表b 的内容插入pos的前面，b 为空。
• reverse()：将链表翻转。
• sort()：将链表排序。
• unique()：将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩，因此一般先排序后去重。

【其他成员函数】

• push_front(x )/push_back(x )：x 从链表头或尾入。
• pop_front()/pop_back()：从链表头或尾出。
• front()/back()：返回链表头或尾元素。
• insert(p ,t)：在p 之前插入t 。
• erase§：删除p 。
• clear()：清空链表。

举个栗子

HDU No. 1276

官方题目地址

题意：

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

样例

输入： 包含多个测试用例，第1行为测试用例数N ，接着为N行新兵人数（不超过5 000）

输出： 单行输出剩下的新兵的最初编号，编号之间有一个空格。

样例

举个栗子

答案就是 1、 7 、19

算法设计

报数问题，使用list解决

1. 定义一个list，将1-n依次放入链表尾部
2. 如果链表中的元素大于3，则计数器cnt = 1，遍历链表，如果cnt ++ % k == 0，则删除当前元素，否则指向下一个继续计数；【首先 k =2报数，报数结束后，再k = 3进行报数，→ 交替】
3. 按顺序输出链表中的元素，以空格隔开，最后换行。

慎用STL的list，空间复杂度和时间复杂度都容易超出限制。

算法实现

#include
#include 

using namespace std;

int main(){
	
	int T , n;
	
	list<int> a;
	
	list<int>::iterator it;
	
	scanf("%d",&T);
	
	while(T --){
		
		scanf("%d",&n);
		
		a.clear();
		
		int k = 2; //2报数
		
		for(int i = 1; i <= n ; i++){
			a.push_back(i);  //存下每个士兵的编号 1- n 
		} 
		
		while(a.size() > 3){
			int cnt = 1;
			for(it = a.begin() ; it != a.end();){
				if(cnt ++ % k == 0){ //删除喊 k的 
					it = a.erase(it);
				}
				else{
					it ++;
				}
			}
			
			k = ( k == 2 ? 3 : 2); //2 、 3交替进行 
		}
		
		for(it = a.begin() ; it != a.end() ; it++){
			if(it != a.begin()){
				printf(" ");
			}
			printf("%d",*it);
		}
		printf("\n");
		
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52