P7955 题解

yeshubo_qwq · 2021-12-02 21:07:51 · 题解

题面传送门

题意

有 n 个阵型，m 个队员，每个队员都有自己能担任的位置，问：哪些阵型可以实现，哪些阵型不可以实现。

思路

整体思路：先按能担任的位置进行计数，然后枚举每种阵型，进行判断。

判断思路：能担任一种职位的就让他担任这个职位，能担任二种职位的，枚举给哪种职位，能担任三种职位的就进行补位。

代码

#include<bits/stdc++.h>
using namespace std;
int n,i,a[11],b[11],c[11],m,d[8],cnt,flag,j,k,i2,j2,k2,t;
string s;
int main(){
    cin>>n;
    for(i=1;i<=n;i++) 
        scanf("%d-%d-%d",&a[i],&b[i],&c[i]);//用scanf读入会比cin方便 
    cin>>m;
    for(i=1;i<=m;i++){
        cin>>s;
        if(s.size()==1){//计数 
            if(s=="O")d[1]++;
            else if(s=="V")d[2]++;
            else d[3]++;
        }
        else if(s.size()==2){
            sort(s.begin(),s.end());//因为可能出现两种情况其实表示同一种（如：NO,ON），所以进行排序 
            if(s=="NO")d[4]++;
            else if(s=="NV")d[5]++;
            else if(s=="OV")d[6]++;
        }
        else d[7]++;
    }
    for(t=1;t<=n;t++){
        flag=0;
        for(i=0;i<=d[4];i++)//枚举NO几人去N 
            for(j=0;j<=d[5];j++)//枚举NV几人去N 
                for(k=0;k<=d[6];k++){//枚举OV几人去O
                    i2=d[4]-i;//NO剩下的人取O 
                    j2=d[5]-j;//NV剩下的人取V
                    k2=d[6]-k;//OV剩下的人取V
                    cnt=0;
                    if(a[t]>(d[1]+k+i2)) cnt+=a[t]-(d[1]+k+i2);//O缺几个加上 
                    if(b[t]>(d[2]+j2+k2))cnt+=b[t]-(d[2]+j2+k2);//V缺几个加上
                    if(c[t]>(d[3]+i+j))  cnt+=c[t]-(d[3]+i+j);//N缺几个加上
                    if(cnt<=d[7]) {//能担任三种职位的足够补位
                        flag=1;//标记 
                        goto DA;//如果可以，直接跳出 
                    }
                }
        DA:;
        if(flag)printf("DA\n");else printf("NE\n");
    }
}