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?<?n ), that pi?>?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;}