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

Slightly Decreasing Permutations

time limit per test

memory limit per test

input

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?

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

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

div+css3阶梯分页样式

div+css3阶梯分页样式

84

查看详情

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

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

AC代码：

#include <iostream>#include <cstdio>#include <string>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-1 ;i++)			printf("%d ", i);		for(int i=n; i>=n-k; i--)			printf("%d ", i);		printf("\n");	}	return 0;}