【集训DAY5】快速排序【模拟】【数学】

思路：

我们直接倒着来判断就行了

#include
#include

using namespace std;

const int MAXN = 50000;

int n, k;
int a[MAXN], ans[MAXN], id[MAXN];

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++) id[i] = i;
	int l = 1, r = n, wh = 1;
	for(int i = 1; i <= n; i ++) {
		int x = a[(i - 1) % k + 1] % (n - i + 1) + l;
		if(id[x] == wh) {
			ans[id[x]] = l;
			swap(id[x], id[l]);
			l ++;
			while(ans[wh]) wh ++;
		}
		else 
		{
			ans[id[x]] = r;
			swap(id[x], id[l]);
			swap(id[l], id[r]);
			r --;
		}
	}
	for(int i = 1; i <= n; i ++) printf("%d\n", ans[i]);
	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