sgu279：Bipermutations(贪心构造)

题目大意：
$~~~~~~$$i\prec j$意味着在序列中$i$的位置在$j$的前面。
$~~~~~~$构造一个长度为$2n$的序列，由$1,1‘,2,2‘...,n,n‘$构成。
$~~~~~~$满足如下条件：
$~~~~~~$$1.$对于任意$i$满足$i‘\prec i$；
$~~~~~~$$2.$对于任意$i \neq j$，满足$i\prec j \Leftrightarrow i‘\prec j‘$；
$~~~~~~$$3.$定义$b_{i,j}=\left\{\begin{matrix} j‘,j<i\\ j,j>i\end{matrix}\right.$，$a_i=\sum [i\prec b_{i,j}]$，给出序列$a$，构造出满足$a$的序列。

分析：
$~~~~~~$很显然我们要倒着填。
$~~~~~~$从$2n$位开始，每次找最小的$i$使得$a_i=0$填在这一位，更新后面的$a$，如果找不到，那就找位置最大的没有填过$i‘$的$i$填在这一位，更新后面的$a$，否则无解。
$~~~~~~$为什么要先考虑$a_i=0$呢？设前者的结果为$c_1$，后者的结果为$c_2$，如果$c_2>c_1$，$c_1$肯定在之前就被$c_2$给更新过，那么两者交换顺序不影响；如果$c_2<c_1$，先放$-c_2$肯定会使$a_{c_1}$变小成负数，不符合题意，因此先考虑显然可以。

AC code：

#include <cstdio>
#include <algorithm>
#define mp make_pair
#define pii pair<int,int>
#define x first
#define y second
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;

const int MAXN = 1009;

int n;
short a[MAXN];
short ans[MAXN<<1];
short vis[MAXN];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", a+i);

    for(int i = (n<<1); i >= 1; --i)
    {
        int c1 = -1, c2 = -1;
        for(int j = 1; j <= n; ++j)
            if(!a[j] && !vis[j])
            {
                c1 = j;
                break;
            }
        if(c1 != -1)
        {
            ans[i] = c1;
            vis[c1] = 1;
            for(int j = 1; j <= n; ++j)
                if(!vis[j] && j < c1)
                    --a[j];
        }
        else
        {
            for(int j = n*2; j > i; --j)
                if(ans[j] > 0 && vis[ans[j]] == 1)
                {
                    c2 = ans[j];
                    break;
                }
            if(c2 == -1)
            {
                puts("NO");
                return 0;
            }
            ans[i] = -c2;
            vis[c2] = 2;
            for(int j = 1; j <= n; ++j)
                if(!vis[j] && j > c2)
                    --a[j];
        }
    }

    puts("YES");
    for(int i = 1; i <= (n<<1); ++i)
        printf("%d ", ans[i]);
    puts("");

    #ifndef ONILNE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}