自动搬运

查看原文

来自洛谷，原作者为

	Larryyu Euphoric NocturNe |AS| ALTERing EGO

搬运于2025-08-24 22:39:56，当前版本为作者最后更新于2022-09-16 15:52:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给你一个01字符串 $s$ ， $s_i=1$ 时， $\forall 1\le j\le i-1,a_i>a_j$ , $s_i =0$ 时， $a_i$ 不满足上述条件，求任一满足条件的 $a$ 数列。

Solution

设字符串 $s$ 中有 $x$ 个0, $y$ 个1，则 $\forall s_i=1,a_i=n-i+1$ ，即升序，既能保证 $a_i>a_j$ ，也能保证 $a_{i_1}<a_{i_2}$ ，再来看 $s_i=0$ 的情况，明显剩下的 $a_j=[1,x]$ ，但是为降序，否则当 $s_1 =0,s_2=0$ 时， 可能$a_1=1,a_2=2$，实际上 $s_1=0,s_2=1$ 造成冲突 。代码很好实现。

Code

int t;
int n;
int a[100100];
string s;
int main(){
    cin>>t;
    while(t--){
        int cnt=0,tot=0;
        cin>>n;
        cin>>s;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='1') tot++;
          //  cout<<a[i];
        }
       	tot=n-tot+1; //不要忘了加一
        cnt=tot-1;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='0'){
                cout<<cnt<<" ";
                cnt--;//递减
            }
            else{
                cout<<tot<<" ";
                tot++;//递增
            }
        }
        cout<<endl;
    }
    return 0;
}

完结撒花！！