D. Optimal Number Permutation

题目连接：

http://www.codeforces.com/contest/622/problem/D

Description

You have array a that contains all integers from 1 to n twice. You can arbitrary permute any numbers in a.

Let number i be in positions xi, yi (xi < yi) in the permuted array a. Let's define the value di = yi - xi — the distance between the positions of the number i. Permute the numbers in array a to minimize the value of the sum .

Input

The only line contains integer n (1 ≤ n ≤ 5·105).

Output

Print 2n integers — the permuted array a that minimizes the value of the sum s.

Sample Input

2

Sample Output

1 1 2 2

Hint

题意

构造题，让构造一个1-n中每个数出现两次的一个序列，使得这个序列的权值和最小

权值 = (n-i)(di+i-n)，di是指第i个数出现两次的距离

题解：

我们猜想一下，我们能不能让di = n-i，这样权值和就是0了

于是就这样构造吧，我们分奇数偶数去摆放，这样就可以错开了，就不会重叠在一起

因为n这个数可以使得(n-i)=0，所以就用它来调整这个序列

唔，如果我题解不是很清楚，可以跑跑我的代码，可以发现出来的结果是两个类似回文串的东西~

喵。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+7;

int a[maxn];

int d[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    int tot = 1;

    for(int i=1;i<=n;i+=2)

        a[tot++]=i;

    int p = n;

    if(p%2==0)p--;

    else p-=2;

    for(int i=p;i>=1;i-=2)

    {

        a[tot++]=i;

    }

    for(int i=2;i<=n;i+=2)

        a[tot++]=i;

    p=n;

    if(p%2==1)p--;

    else p-=2;

    for(int i=p;i>=1;i-=2)

        a[tot++]=i;

    a[tot++]=n;

    int Ans=0;

    /*

    for(int j=1;j<=2*n;j++)

    {

        if(d[a[j]])

            Ans+=(n-a[j])*abs(j-d[a[j]]+a[j]-n);

        else

            d[a[j]]=j;

    }

    cout<<Ans<<endl;

    */

    for(int i=1;i<=2*n;i++)

        cout<<a[i]<<" ";

    cout<<endl;

}