Codeforces Round #175 (Div. 2)-A. Slightly Decreasing Permutations_html/css_WEB-ITnose

Slightly Decreasing Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Permutation p is an ordered set of integers p1,??p2,??…,??pn, consisting of n distinct positive integers, each of them doesn’t exceed n. We’ll denote the i-th element of permutation p as pi. We’ll call number n the size or the length of permutation p1,??p2,??…,??pn.

The decreasing coefficient of permutation p1,?p2,?…,?pn is the number of such i (1?≤?i??pi?+?1.

You have numbers n and k. Your task is to print the permutation of length n with decreasing coefficient k.

Input

The single line contains two space-separated integers: n,?k (1?≤?n?≤?105,?0?≤?k?<?n ) ? the permutation length and the decreasing coefficient.

立即学习“前端免费学习笔记（深入）”；

Output

In a single line print n space-separated integers: p1,?p2,?…,?pn ? the permutation of length n with decreasing coefficient k.

If there are several permutations that meet this condition, print any of them. It is guaranteed that the permutation with the sought parameters exists.

Sample test(s)

input

5 2

登录后复制

output

1 5 2 4 3

登录后复制

input

3 0

登录后复制

output

1 2 3

登录后复制

input

3 2

登录后复制

output

3 2 1

登录后复制

解题思路：就是让生成n个数排列，并且保证刚好有k个 pi > p(i+1)。

贪心。直接考虑如何构造那k个相邻的逆序，其实最少只要k+1个书即可构造出所需的相邻逆序，直接把k+1个数倒序排即可。但是要把剩下的n-k-1个升序放在前面输出，然后再输出相邻逆序即可。

AC代码：

#include #include #include using namespace std;int a[100005];int main(){//freopen("in.txt", "r", stdin);int n, k;while(scanf("%d%d", &n, &k)==2){int t = 1, tt = n;for(int i=1; i=n-k; i--)printf("%d ", i);printf("\n");}return 0;}

登录后复制