CF1473C No More Inversions

No More Inversions - 洛谷

题目描述

You have a sequence aa with nn elements 1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)1,2,3,…,k−1,k,k−1,k−2,…,k−(n−k) ( k \le n < 2kk≤n<2k ).

Let's call as inversion in aa a pair of indices i < ji<j such that a[i] > a[j]a[i]>a[j] .

Suppose, you have some permutation pp of size kk and you build a sequence bb of size nn in the following manner: b[i] = p[a[i]]b[i]=p[a[i]] .

Your goal is to find such permutation pp that the total number of inversions in bb doesn't exceed the total number of inversions in aa , and bb is lexicographically maximum.

Small reminder: the sequence of kk integers is called a permutation if it contains all integers from 11 to kk exactly once.

Another small reminder: a sequence ss is lexicographically smaller than another sequence tt , if either ss is a prefix of tt , or for the first ii such that s_i \ne t_isi​=ti​ , s_i < t_isi​<ti​ holds (in the first position that these sequences are different, ss has smaller number than tt ).

输入格式

The first line contains a single integer tt ( 1 \le t \le 10001≤t≤1000 ) — the number of test cases.

The first and only line of each test case contains two integers nn and kk ( k \le n < 2kk≤n<2k ; 1 \le k \le 10^51≤k≤105 ) — the length of the sequence aa and its maximum.

It's guaranteed that the total sum of kk over test cases doesn't exceed 10^5105 .

输出格式

For each test case, print kk integers — the permutation pp which maximizes bb lexicographically without increasing the total number of inversions.

It can be proven that pp exists and is unique.

=========================================================================

这种题要是细究原理那就真是摸不着头脑了，直接观察样例

n=k的时候，排列保持不变

n=k+1的时候，顺序排序的后两位被翻转，或者被交换

我们至少是可以猜到，n和k的差值，决定了多少元素被交换或者被翻转。

这里的多少可以是n-k的二倍也可以是n-k+1个元素，我们先一个一个猜测，

手写一个n=k+2的情况， p=1 2 3变成了  3 2 1

看来完全可以确定不是交换，而是n-k+1个元素完全被翻转，不是n-k的二倍个元素，而是n-k+1个元素

也就是说，题目要是多给一个样例这个题连A题都算不上了

# include<bits/stdc++.h>
# define mod 10
using namespace std;
typedef long long int ll;



int main ()
{

    int t;

    cin>>t;

    while(t--)
    {
        int n,k;

        cin>>n>>k;

        for(int i=1;i<=k-(n-k)-1;i++)
        {
            cout<<i<<" ";

        }

        for(int i=k;i>=k-(n-k);i--)
        {
            cout<<i<<" ";

        }
        cout<<'\n';


    }


    return 0;

}