[CF1360H] Binary Median - 贪心

Description

一共有 \(2^m\) 个长度为 \(m\) 的 01 字符串，求从中删去 \(n\) 个后，求剩下 \(2^m-n\) 个二进制数按照字典序排序后的中位数。若有偶数个数，则取中间靠左的数作为这 \(2^m -n\) 个二进制数的中位数。\(T \le 1000, n \le 100, m \le 60\)

Solution

模拟一个 Kth 的过程，显然 \(k=[\frac {n+1} 2]\)，从高到低枚举依次确定各位，假设现在枚举到了第 \(p\) 位，检查第 \(p\) 位为 \(0\) 时数字的个数，如果个数 \(\le k\) 则将第 \(p\) 位定为 \(0\)，否则定为 \(1\) 并减去这个已经统计出的个数

时间复杂度 \(O(Tnm^2)\)，其实也可以用位运算压到 \(O(Tnm \log m)\)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

int n,m;
string s[N];
int a[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(auto &j:s[i])
        {
            j-=‘0‘;
        }
    }
    memset(a,0,sizeof a);
    int k=(1ll<<m)-n;
    k=(k+1)/2;
    for(int i=0;i<m;i++)
    {
        int res=1ll<<(m-i-1);
        for(int j=1;j<=n;j++)
        {
            int flag=1;
            for(int k=0;k<=i;k++)
            {
                if(s[j][k]!=a[k])
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                res--;
            }
        }
        if(k>res)
        {
            k-=res;
            a[i]=1;
        }
    }
    for(int i=0;i<m;i++)
    {
        cout<<a[i];
    }
    cout<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

[CF1360H] Binary Median - 贪心

原文：https://www.cnblogs.com/mollnn/p/13620660.html