当前位置：网站首页>【集训DAY5】快速排序【模拟】【数学】

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

2022-08-09 22:35:00 【VL——MOESR】

在这里插入图片描述

思路：

我们直接倒着来判断就行了
在这里插入图片描述

#include<iostream>
#include<cstdio>

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;
}
原网站

版权声明
本文为[VL——MOESR]所创，转载请带上原文链接，感谢
https://blog.csdn.net/liuziha/article/details/126253896

边栏推荐

猜你喜欢

随机推荐