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

WBOY
發布: 2016-06-24 11:55:01
原創
1352 人瀏覽過

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?

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 <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; i--)			printf("%d ", i);		printf("\n");	}	return 0;}</string></cstdio></iostream>
登入後複製

 


來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板