CodeForces1138B.Circus

题目链接:CodeForces1138B.Circus

题意:

给n个人,每个人可扮演的角色有0,1,2个,然后需要将这n个人均分为两部分,要求集合A中的人中能扮演角色A的人数和集合B中的人中能扮演角色B的人数相等。

题解:

一直以为是贪心,结果只需要暴力解方程就可以了。

设集合A中的人有tot0个人什么都不会,tot1个人只会一扮演一个,tot2的人都能扮演。然后用sum表示能扮演B的人数。

枚举tot0,我们假设存在合法解的时候,可以推出tot1=(n/2-tot0)*2-sum,tot2=sum-(n/2-tot0)。然后分配即可。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,sum;
int TOT0=0,TOT1=0,TOT2=0;
int a[5009],b[5009],c[5009];
char s[5009];
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        a[i]=(s[i]=='1');
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        b[i]=(s[i]=='1');
    for(int i=1;i<=n;i++)
    {
        c[i]=a[i]+b[i];
        sum+=b[i];
    }
    for(int i=1;i<=n;i++)
        switch (c[i])
        {
            case 0:TOT0++;break;
            case 1:TOT1++;break;
            case 2:TOT2++;break;
        }
    vector<int> ans;
    ans.clear();
    for(int tot0=0;tot0<=TOT0;tot0++)
    {
        
        int tot1=2*(n/2-tot0)-sum;
        int tot2=sum-(n/2-tot0);
        if(tot0+tot1+tot2!=n/2)
            continue;
        if(tot1<0||tot1>TOT1||tot2<0||tot2>TOT2)
            continue;
        for(int i=1;i<=n;i++)
        {
            switch(c[i])
            {
                case 0:
                    if(tot0)
                    {
                        tot0--;
                        ans.push_back(i);
                    }
                break;
                case 1:
                    if(tot1)
                    {
                        tot1--;
                        ans.push_back(i);
                    }
                break;
                case 2:
                    if(tot2)
                    {
                        tot2--;
                        ans.push_back(i);
                    }
                break;
            }
        }
        break;
    }
    for(auto v:ans)
        printf("%d ",v);
    if(ans.empty())
        puts("-1");
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。