Codeforces 873D Merge Sort 题解

发表于 | 更新于 | 阅读次数：
本文字数： 366 字 | 阅读时长 ≈ 1 分钟

题意简述

给定$n,k$，求一个长度为$n$的数列，使得对它进行归并排序要调用$k$次$MergeSort$函数。

注：$MergeSort$：对$l,mid$和$mid,r$进行分治操作，如果有序，直接返回（不过也是要算一次调用）。否则就合并一下再返回。

思路（水题，一句解决）

初始化为$1,2,3…n$，写一个归并出来，如果要多一次操作，只要把左右两半的第一个位置换一下即珂，然后左右分别操作求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    int n,k;
    void Input()
    {
        cin>>n>>k;
    }

    int a[N];
    void Sort(int l,int r) //精髓
    {
        if (!k or l>=r-1) return;

        int mid=(l+r)>>1;
        swap(a[mid-1],a[mid]);
        --k;
        Sort(l,mid);Sort(mid,r);
    }
    void Soviet()
    {
        if (k%2==0) return (void)puts("-1");
        k/=2;

        F(i,1,n) a[i]=i;
        Sort(1,n+1);
        if (k) return (void)puts("-1");
        else
        {
            F(i,1,n) printf("%d ",a[i]);
            putchar('\n');
        }

    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w