题解 | #B problem#

问题分析：

每次比赛总共n个人，每次选任意两个未被淘汰的人对决

分数不同：分数低的淘汰

分数相同：两个人同时被淘汰

目的：如果某个人可能存活到最后就输出1，否则输出0

也就是说，当一组数据里面最大值存在奇数个时，只需要他和别的人比较，最后只会剩下他自己，

所以只有最大值输出1，其他为0；当一组数据里面存在偶数个最大值时，用最大值与其他数比较，

最后只会剩下一一对应的最大值，如果任选一个数留到除了最大值以外的最后，最大值再同时淘

汰，那么这个数就会存活到最后，也就是任何一个不是最大值的数都可以存活到最后，最大值都

会被淘汰。

代码实现：

#include<bits/stdc++.h>

using namespace std;

int main() {

int T;
cin >> T;
for(int i=0;i<T;i++)
{
    int n;
    cin >> n;
    vector<int>a(n);
    int mx=0;
    map<int,int>mp;
    for(int j=0;j<n;j++)
    {
        cin >> a[j];
        mx=max(mx,a[j]);
        mp[a[j]]++;
    }
    int f=mp[mx]%2;
    for(int j=0;j<n;j++)
    {
        if(f==1)
        {
            if(a[j]==mx)
            {
                cout << 1;
            }
            else
            {
                cout << 0;
            }
        }
        else
        {
            if(a[j]<mx)
            {
                cout << 1;
            }
            else
            {
                cout << 0;
            }
        }
    }
    cout << '\n';
}
return 0;

}

时间复杂度为O(nlogn);