2012

第一题

时间复杂度：$O(n)$
空间复杂度：$O(n)$

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
const int N = 100010;
int n;
int a[N];
int temp[N];

void print()
{
	for(int i = 1; i <= n; i ++ ) cout << a[i] << " ";
	cout << endl;
}

void solve()
{
	int idx = 0;
	for(int i = 1; i <= n; i ++ ) 
		if(a[i] % 2 != 0)
			temp[ ++ idx] = a[i];

	for(int i = 1; i <= n; i ++ )
		if(a[i] % 2 == 0)
			temp[ ++ idx] = a[i];

	for(int i = 1; i <= n; i ++ )
		a[i] = temp[i];
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ ) cin >> a[i];
	solve();
	print();

	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
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

char t[N], s[N], temp[N];
int idx;
int pos;
int n, m;

// char *function(){} 用于返回字符数组 
void insert(char *t,char *s, int pos)
{
	int n = 0, m = 0;  // n记录t的长度，m记录s的长度 
	char *tt = t, *ts = s;
	while(*t != '\0')  // 计算t的长度 
	{
		n ++ ;
		t ++ ;
	}

	while(*s != '\0')  // 计算s的长度 
	{
		m ++ ;
		s ++ ;
	} 

	t = tt, s = ts;

	// 将t中[0, pos - 1]插入temp中 
	for(int i = 0; i < pos; i ++ ) 
		temp[idx ++ ] = t[i];

	// 将 s插入temp中
	for(int i = 0; i < m; i ++ )
		temp[idx ++ ] = s[i];

	// 将t中剩下的插入
	for(int i = pos; i < n; i ++ )
		temp[idx ++ ] = t[i];

	// 将temp赋值给t
	for(int i = 0; i < idx; i ++ )
		t[i] = temp[i];
}

int main()
{
	cin >> t >> s >> pos;

	insert(t, s, pos);

	cout << t << endl;

	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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;

struct Node
{
	int val;
	Node *left, *right;

	Node(): left(NULL), right(NULL) {}
	Node(int _val): val(_val), left(NULL), right(NULL) {}
};

// 传参的时候一定要用 Node* &root，如果用 Node* root 那么传入的指针就变为形参了
void create(Node* &root, int x)
{
	// 如果左右满足条件并且有子树 
	if(root->val > x && root->left != NULL) create(root->left, x);
	if(root->val < x && root->right != NULL) create(root->right, x);	

	// 如果左右满足条件并且无子树
	if(root->val > x && root->left == NULL) 
	{
		root->left = new Node(x);
		return;
	}
	if(root->val < x && root->right == NULL) 
	{
		root->right = new Node(x);
		return;
	}
}

void print(Node *root)  // 先序遍历
{
	cout << root->val << " ";
	if(root->left) print(root->left);
	if(root->right) print(root->right);
} 

int find(Node *root ,int x, int d)
{
	if(root->val == x) 
	{
		return d;
	}

	// 满足条件且左子树或右子树不为空 
	// 注意要链式返回return 
	if(root->val > x && root->left) return find(root->left, x, ++ d);  
	if(root->val < x && root->right) return find(root->right, x, ++ d);

	return -1;  // 说明没有这个值 
}

int main()
{
	cin >> n;
	int x;
	cin >> x;
	Node *root = new Node(x);  // 创建树根 

	for(int i = 1; i < n; i ++ )  // 创建二叉排序树 
	{
		int x;
		cin >> x;
		create(root, x);
	}

	// print(root);

	int d = 1;
	cin >> x;
	cout << find(root, x, d) << endl;

	return 0;
}

2013

第一题

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

char stk[N], q[N];  // stk:栈，q:队列
char a[N];

bool judge_stack(char *a, int len)  // 用栈进行判断
{
	int half = len / 2;  // 折半
	int tt = 0;
	for(int i = 0; i < half; i ++ )
	{
		stk[ ++ tt] = *a;
		a ++ ;
	} 

	if(len % 2 != 0) a ++ ;  // 如果字符长度为奇数，下标就要往后移动一位

	for(int i = 0; i < half; i ++ )
	{
		char top = stk[tt -- ];  // 取出栈顶	 
		if(top != *a) return false;  // 如果不匹配，则匹配失败

		a ++ ;  // 否则移动一位继续匹配 
	} 

	return true;
}

bool judge_queue(char *a, int len)  // 用队列判断
{
	char *t = a;

	int hh = 0, tt = -1;
	int half = len / 2;
	for(int i = 0; i < half; i ++ )
	{
		q[ ++ tt] = *a;
		a ++ ;
	}

	int flag = 0;
	if(len % 2 != 0) flag = 1 ;  // 判断是否为奇数

	a = t;

	for(int i = len - 1; i > len / 2 + flag; i -- )
	{
		char val = q[hh ++ ];
		if(val != a[i]) return false;
	}

	return true;
}

int main()
{
	char t;
	int len = 0;
	while(cin >> t, t != '@')
	{
		a[len ++ ] = t;
	}

	cout << judge_stack(a, len) << endl;

	cout << judge_queue(a, len) << endl;

	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
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int x;
struct Node
{
	int val;
	Node *left, *right;

	Node(): left(NULL), right(NULL) {}
	Node(int _val): val(_val), left(NULL), right(NULL) {}
};

void insert(Node* &root, int x)
{
	if(root->val > x && root->left != NULL) insert(root->left, x);
	if(root->val < x && root->right != NULL) insert(root->right, x);

	if(root->val > x && root->left == NULL)
	{
		Node *node = new Node(x);
		root->left = node;
	}

	if(root->val < x && root->right == NULL)
	{
		Node *node = new Node(x);
		root->right = node;
	}
}

bool find(Node *root, int x)
{
	if(root->val == x) return true;
	if(root->val > x && root->left != NULL) return find(root->left, x);
	if(root->val < x && root->right != NULL) return find(root->right, x);

	return false;
}

int main()
{
	cin >> n;
	cin >> x;
	Node *root = new Node(x);
	for(int i = 1; i < n; i ++ )
	{
		cin >> x;
		insert(root, x);
	}

	cin >> x;
	if(find(root, x)) puts("YES");
	else puts("NO");

	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
53
54
55
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, v;
int g[N][N];
int dist[N];
bool st[N];

void dijkstra(int v)
{
	memset(dist, 0x3f, sizeof dist);
	dist[v] = 0;

	for(int i = 0; i < n; i ++ )
	{
		int t = -1;
		for(int j = 1; j <= n; j ++ )
			if(!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;

		st[t] = true;

		for(int j = 1; j <= n; j ++ )
			if(dist[j] > dist[t] + g[t][j])
				dist[j] = dist[t] + g[t][j];
	}
}

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

	memset(g, 0x3f, sizeof g);

	while(m -- )
	{
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c);
	}

	dijkstra(v);

	long long sum = 0;
	for(int i = 1; i <= n; i ++ ) sum += dist[i];
	cout << sum << endl;

	return 0;
}

2014

第一题

1

第二题

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
int x;

struct Node
{
	int val;
	Node *left, *right;

	Node(): left(NULL), right(NULL) {}
	Node(int _val): val(_val), left(NULL), right(NULL) {}
};

void insert(Node* &root, int x)
{
	if(root->val > x && root->left != NULL) insert(root->left, x);
	if(root->val < x && root->right != NULL) insert(root->right, x);

	if(root->val > x && root->left == NULL)
	{
		Node *root = new Node(x);
		root->left = root;
	}

	if(root->val < x && root->right == NULL)
	{
		Node *root = new Node(x);
		root->right = root;
	}
}

Node *find(Node *root, int x)
{
	if(root->val == x) return root;

	if(root->val > x && root->left != NULL) return find(root->left, x);
	if(root->val < x && root->right != NULL) return find(root->right, x);

	if(root->val > x && root->left == NULL) return NULL;
	if(root->val < x && root->right == NULL) return NULL;
}

int main()
{
	cin >> n;
	cin >> x;
	Node *root = new Node(x);
	for(int i = 1; i < n; i ++ )
	{
		cin >> x;
		insert(root, x);
	}

	cin >> x;
	Node *res = find(root, x);

	if(res == NULL) puts("NULL");
	else cout << res->val << endl;

	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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int tree[N];  // -1表示空节点 

// 前序遍历
void preorder(int u)
{
	cout << tree[u] << " ";
	if(tree[2 * u] != -1 && 2 * u <= n) preorder(2 * u);
	if(tree[2 * u + 1] != -1 && 2 * u + 1 <= n) preorder(2 * u + 1);
}

// 中序遍历
void inorder(int u)
{
	if(tree[2 * u] != -1 && 2 * u <= n) inorder(2 * u);
	cout << tree[u] << " ";
	if(tree[2 * u + 1] != -1 && 2 * u + 1 <= n) inorder(2 * u + 1);
}

// 后序遍历 
void postorder(int u)
{
	if(tree[2 * u] != -1 && 2 * u <= n) postorder(2 * u);
	if(tree[2 * u + 1] != -1 && 2 * u + 1 <= n) postorder(2 * u + 1);
	cout << tree[u] << " ";
}

// 查找x在第几层 
int find(int u, int x)
{
	int t = 0;
	for(int i = 1; i <= n; i ++ ) 
		if(tree[i] == x)
		{	
			t = i;
			break;
		}

	if(t == 0) return -1;

	int floor = 1;
	while(t / 2)
	{
		floor ++ ;
		t /= 2;
	}

	return floor;
}

int main()
{
	cin >> n;
	memset(tree, -1, sizeof tree);
	for(int i = 1; i <= n; i ++ ) cin >> tree[i];

	preorder(1);
	cout << endl;

	inorder(1);
	cout << endl;

	postorder(1);
	cout << endl;

	int x;
	cin >> x;
	cout << find(1, x) << endl;

	return 0;
}

2015

第一题

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
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int stk[N], tt;  // tt表示栈顶，为-1时栈为空 

void init()
{
	tt = -1;
}

bool Is_empty()
{
	return tt == -1;
}

void Push(int x)
{
	stk[ ++ tt] = x;
}

int Get()
{
	return stk[tt -- ];
}

void Transform(int x)
{
	init();  // 将栈初始化 
	while(x / 8)
	{
		int t = x % 8;
		Push(t);
		x /= 8;
	}

	if(x % 8 != 0) Push(x);
}

int main()
{
	int x;
	cin >> x; 

	Transform(x);

	while(!Is_empty())
	{
		cout << Get();
	}
	cout << endl;

	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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node
{
	int val;
	Node *left, *right;

	Node(): left(NULL), right(NULL) {}
	Node(int _val): val(_val), left(NULL), right(NULL){}
};

void build(Node* &root, int deep)
{
	cout << "当前在第：" << deep << "层" << endl;
	Node *left_node = new Node();
	Node *right_node = new Node();

	cout << "输入左、右的值（输入-1则置为空节点）" << endl;
	int left_val, right_val;
	cin >> left_val >> right_val;

	if(left_val != -1)
	{
		left_node->val = left_val;
		root->left = left_node;
		build(left_node, ++ deep);
		deep -- ;
	}

	if(right_val != -1)
	{
		right_node->val = right_val;
		root->right = right_node;
		build(right_node, ++ deep);
		deep -- ;
	}
}

// 前序 
void preorder(Node* &root)
{
	cout << root->val << " ";
	if(root->left != NULL) preorder(root->left);
	if(root->right != NULL) preorder(root->right);
}

// 中序 
void inorder(Node* &root)
{
	if(root->left != NULL) inorder(root->left);
	cout << root->val << " ";
	if(root->right != NULL) inorder(root->right);
}

// 后序 
void postorder(Node* &root)
{
	if(root->left != NULL) postorder(root->left);
	if(root->right != NULL) postorder(root->right);
	cout << root->val << " ";
}

// 清除 
bool delete_tree(Node* &root)
{
	if(root->left != NULL) delete_tree(root->left);	
	if(root->right != NULL) delete_tree(root->right);

	delete root;
}

/*
   1 
   2 3 
   4 5 6 7
 */

int main()
{
	cout << "输入根节点的值" << endl;
	int x;
	cin >> x; 
	Node *root = new Node(x);
	build(root, 2);

	if(root != NULL) preorder(root);
	cout << endl;

	if(root != NULL) inorder(root);
	cout << endl;

	if(root != NULL) postorder(root);
	cout << endl;

	delete_tree(root);
	root = NULL;

	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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m, Size;
int a[N];

void down(int u)
{
	int t = u;
	if(2 * u <= Size && a[t] < a[2 * u]) t = 2 * u;
	if(2 * u + 1 <= Size && a[t] < a[2 * u + 1]) t = 2 * u + 1;

	if(t != u)
	{
		swap(a[t], a[u]);
		down(t);
	}
}

int main()
{
	cin >> n >> m;
	Size = n;
	for(int i = 1; i <= n; i ++ ) cin >> a[i];

	for(int i = n / 2; i >= 1; i -- ) down(i);

	while(m -- )
	{
		cout << a[1] << " ";
		swap(a[1], a[Size]);
		Size -- ;
		down(1);
	}
	cout << endl;
	return 0;
}

2016

第一题

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

// ¶¨Òå˳ÐòÕ»£¬topΪջ¶¥£¬top == -1ʱΪ¿Õ 
char stk[N];
int top = -1;

struct Node
{
	char val;
	Node *next;

	Node(): next(NULL) {}
	Node(char _val): val(_val), next(NULL) {}
};


// Õ»Ïà¹Ø 
void Init_stack()
{
	top = -1;
}

void Push_stack(char x)
{
	stk[ ++ top] = x;
}

char Top_stack()
{
	char t = stk[top];
	top -- ;
	return t;
}

bool Is_empty_stack()
{
	return top == -1;
}

bool Judge_stack(char str[])
{
	int len = strlen(str);
	int mid = len / 2;
	int flag = 0;
	if(len % 2 == 0) flag = 0;
	else flag = 1;

	Init_stack();
	for(int i = 0; i < mid; i ++ ) Push_stack(str[i]);

	for(int i = mid + flag; i < len; i ++ )
		if(Top_stack() != str[i])
			return false;

	return true;
}


// ¶ÓÁÐÏà¹Ø 
void Init_queue(Node* &front, Node* &rear)
{
	Node* t;
	while(front->next != NULL)
	{
		t = front;
		front = front->next;
		delete t;
	}
	front = new Node();
	rear = front;
}

void Print_queue(Node *front)
{
	if(front->next != NULL) front = front->next;
	else return;
	while(front != NULL)
	{
		cout << front->val << " ";
		front = front->next;
	}
	cout << endl;
}

void Push_queue(Node* &rear, char x)
{
	Node *node = new Node(x);
	rear->next = node;
	rear = rear->next;
}

char Front_queue(Node* &front, Node* &rear)
{
	if(front == NULL) return '-1';

	char res = front->val;
	Node* t = front;
	if(front->next != NULL)
	{
		front = front->next;
		delete t;
	} 
	else Init_queue(front, rear);

	return res;
}

bool Judge_queue(Node* &front, Node* &rear, char str[])
{
	int len = strlen(str);
	int mid = len / 2;
	int flag = 0;
	if(len % 2 == 0) flag = 0;
	else flag = 1;

	Init_queue(front, rear);

	for(int i = 0; i < mid; i ++ )
		Push_queue(rear, str[i]);

	if(front->next != NULL) front = front->next;
	// ʹµÃfrontÍùºóÒƶ¯Ò»Î» 
	// ÒòΪ³õʼ»¯µÄʱºòfrontµÈÓÚÒ»¸ö¿Õ½Úµã 

	for(int i = len - 1; i >= mid + flag; i -- )
	{
		char t = Front_queue(front, rear);
		if(t != str[i])
			return false;
	}

	return true; 
}

int main()
{
	Node *front = new Node();
	Node *rear = front;

	char str[N];
	cin >> str;
	cout << Judge_stack(str) << endl;
	cout << Judge_queue(front, rear, str) << endl;

}

第二题

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node
{
	int val;
	Node *left, *right;

	Node(): left(NULL), right(NULL) {}
	Node(int _val): val(_val), left(NULL), right(NULL) {}
};

void build(Node* &root, int deep)
{
	cout << "输入第" << deep << "层的左右节点值（-1表示为空）：" << endl;
	int left_val, right_val;
	cin >> left_val >> right_val;

	if(~left_val) 
	{
		Node *left_node = new Node(left_val);
		root->left = left_node;
		build(root->left, ++ deep);
		deep -- ; 
	} 
	if(~right_val) 
	{
		Node *right_node = new Node(right_val);
		root->right = right_node;
		build(root->right, ++ deep);
		deep -- ; 
	} 
}

void preorder(Node *root)
{
	cout << root->val << " ";
	if(root->left != NULL) preorder(root->left);
	if(root->right != NULL) preorder(root->right);
}

void inorder(Node *root)
{
	if(root->left != NULL) inorder(root->left);
	cout << root->val << " ";
	if(root->right != NULL) inorder(root->right);
}

void postorder(Node *root)
{
	if(root->left != NULL) postorder(root->left);
	if(root->right != NULL) postorder(root->right);
	cout << root->val << " ";
}

// flag表示当前节点为父节点的左/右儿子，1为左，2为右 
// last表示上一层的节点 
void delete_tree(Node* &last, Node* &root, int flag)
{
	if(root->left != NULL) delete_tree(root, root->left, 1);
	if(root->right != NULL) delete_tree(root, root->right, 2);

	// 由于是递归处理，执行到此句时一定是根节点往父节点走 
	if(flag == 1) delete last->left;  // 如果当前节点为父节点的左儿子，从父节点删除此节点 
	else delete last->right;
}

int main()
{
	int x;
	cout << "输入树根节点的值：" << endl;
	cin >> x;
	Node *root = new Node(x);

	build(root, 2);

	preorder(root);
	puts("");

	inorder(root);
	puts("");

	postorder(root);
	puts("");

	delete_tree(root, root, 0); 
	delete root;

	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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 80010;

int a[N], Size;
int n, m;

void down(int u)
{
	int t = u;
	if(u * 2 <= Size && a[t] < a[u * 2]) t = u * 2;
	if(u * 2 + 1 <= Size && a[t] < a[u * 2 + 1]) t = u * 2 + 1;
	if(t != u)
	{
		swap(a[t], a[u]);
		down(t);
	}
}

int main()
{
	cin >> n >> m;
	Size = n;
	for(int i = 1; i <= n; i ++ ) cin >> a[i];

	for(int i = n / 2; i >= 1; i -- ) down(i);

	while(m -- )
	{
		cout << a[1] << " ";
		a[1] = a[Size];
		Size -- ;
		down(1);
	}

	return 0;
}