洛谷P8168

TMM233 · 2023-11-13 23:54:59 · 题解

这是一个构造题

如果熟悉二分查找的话，我们可以注意到我们总是先搜索中点，再搜索左右区间：

既然这样，那我们优先考虑把字符串中值为 true 的数字按照从小到大的顺序放在区间中点这样子，我们就可以保证这些数字二分查找的结果一定是正确的。

代码如下

    vector<ll> ton;// 用桶装 true 的项
        stack<ll> ton2;// 用桶装 false 的项
        ton.push_back(-1);
        vector<ll> ans(n+1,-1);
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='1')
            ton.push_back(i);
            else
            ton2.push(i);
        }
        // 把字符串中值为 true 的数字按照从小到大的顺序放在区间中点
        auto build=[&](auto self,ll l,ll r,ll ton_l,ll ton_r)->void{
            if(ton_l>ton_r) return; 
            ll mid=(l+r)>>1;
            if(ton_l==ton_r)
            {
                ans[mid]=ton[ton_l];
                return;
            }
            ll ton_mid=(ton_l+ton_r)>>1;
            ans[mid]=ton[ton_mid];
            self(self,l,mid-1,ton_l,ton_mid-1);
            self(self,mid+1,r,ton_mid+1,ton_r);
        };
        build(build,1,n,1,ton.size()-1);

之后我们考虑处理字符串中值为 false 的数字。题目中要求 S[p]\le1，对此我们不一定需要找到最优解，只要保证 S[p]\le1 即可。考虑将剩余的数字按从大到小的顺序填充进入剩下的空位，因为一个序列递增一个序列递减，那么最多就只能卡住一个数字，因此有 S[p]\le1。

完整代码如下

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define IOS ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll; 
typedef pair<ll,ll> p;
const int N=2e5+5;
int main()
{
    IOS;
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        string s;
        cin>>s;
        s=' '+s;
        vector<ll> ton;// 用桶装 true 的项
        stack<ll> ton2;// 用桶装 false 的项
        ton.push_back(-1);
        vector<ll> ans(n+1,-1);
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='1')
            ton.push_back(i);
            else
            ton2.push(i);
        }
        // 把字符串中值为 true 的数字按照从小到大的顺序放在区间中点
        auto build=[&](auto self,ll l,ll r,ll ton_l,ll ton_r)->void{
            if(ton_l>ton_r) return; 
            ll mid=(l+r)>>1;
            if(ton_l==ton_r)
            {
                ans[mid]=ton[ton_l];
                return;
            }
            ll ton_mid=(ton_l+ton_r)>>1;
            ans[mid]=ton[ton_mid];
            self(self,l,mid-1,ton_l,ton_mid-1);
            self(self,mid+1,r,ton_mid+1,ton_r);
        };
        build(build,1,n,1,ton.size()-1);
        for(int i=1;i<=n;i++)
        {
            if(ans[i]==-1)
            {
                ans[i]=ton2.top();
                ton2.pop();
            }
        }
        for(int i=1;i<=n;i++)
        {
            cout<<ans[i]<<(i==n?'\n':' ');
        }
    }
}