题解 | 小红的排列构造②

#include <stdio.h>
#include <string.h>
//1、字符串s的末尾s[n-1]为'1'，则满足排列,为'0'则不满足;
//2、如果是s[0] == '1',那排列第一个就是1；
//3、如果是001或者010001这种类型，则制定规则为001对应231，即0对应的是位数+2,1对应的是最开始0的位数+2;010001后一个1对应的是前一个1后面最开始0的位数+2;
//4、如果是对应的0011这种类型，后面那个1对应的就是位数+1;
int main() {
    int n;
    scanf("%d",&n);
    char s[100001];
    scanf("%s",s);
    int num[100000];
    int i,j;
    int flag = 0,flag1 = 0;
    int lenth = strlen(s);
    for(i=0;i<lenth;i++)
    {
        int k = 0;
        if(s[i] == '1' && i == 0) 
        {
            num[i] = 1;  //2、如果是s[0] == '1',那排列第一个就是1；
        }
        else if(s[i] == '1' && i > 0 && s[i-1] == '1')
        {
            num[i] = i+1; //4、如果是对应的0011这种类型，后面那个1对应的就是位数+1;
        }
        else if(s[i] == '1' && i > 0 && s[i-1] == '0')
        {
            for(j=i-1;j>=0;j--)
            {     //3、如果是001或者010001这种类型，则制定规则为001对应231，即0对应的是位数+2
                if(s[j] == '0')  
                num[j] = j + 2;
                else if(s[j] == '1')
                {
                    k = j;  //1对应的是最开始0的位数+2;
                    flag1 = 1;
                    break;
                }
            }
            if(flag1 == 1) num[i] = k + 2; //1对应的是最开始0的位数+2;
            else num[i] = 1;
        }
        if(s[lenth-1] == '1')  flag =1;
    }
    if(flag == 1)  //1、字符串s的末尾s[n-1]为'1'，则满足排列,为'0'则不满足;
    {
        for(i=0;i<n;i++)
        {
            printf("%d ",num[i]);
        }
    }
    else printf("-1");
    return 0;
}