CF727D

Eirikr_ · 2024-01-26 18:24:36 · 题解

思路

先把一定要分配的分配了，剩下的就是一个 2-SAT 问题。

或者我们可以不用考虑那么复杂——也许就是个贪心。

注：下面的“人”指的是可以有两种选择的人。

因为每个人都只有可能选择两款相邻的尺码，我们按每个人第一款尺码从小到大排序后从小到大贪心地分配各个款式的衣服即可，即优先分配尺码小的衣服，不够了再分配尺码大的。

其它真的就没了。

一些字符串操作

t.find(",",0) 返回字符串 t 中第一个 , 的下标。

t.substr(0, pos) 取出下标范围内的子串，返回值为 string。

/*
CB Ntsc
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second

#define err cerr<<"Error"
#define rd read()
// #define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out)
{
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}

const int INF = 1e9;
const int N = 2e6+5;
const int M = 1e6+5;
const int S=1e6+5;
const int maxlog = 10;
string ds[10]={"S","M","L","XL","XXL","XXXL"};
struct node{
    int a,b,id;
}p[N];
int tot;
int ans[N];
int c[N],n;
void cal(string s,int id,int f,int idx){
    for(int i=0;i<6;i++){
        if(ds[i]==s){
            if(f==1)p[id].a=i,p[id].id=idx;
            if(f==2)p[id].b=i,p[id].id=idx;
            if(!f){
                ans[idx]=i;
                c[i]--;
                if(c[i]<0){
                    cout<<"NO"<<endl;
                    exit(0);
                }
                return ;
            }

        }
    }
}
bool cmp(node a,node b){
    return a.a<b.a;
}

signed main(){
    for(int i=0;i<6;i++)c[i]=rd;
    n=rd;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        int pos=s.find(",",0);
        if(pos==EOF){
            cal(s,0,0,i);
        }else{
            cal(s.substr(0,pos),++tot,1,i);
            cal(s.substr(pos+1,s.size()-1),tot,2,i);
        }

    }

    // for(int i=1;i<=tot;i++){
    //  cerr<<p[i].a<<' '<<p[i].b<<endl;
    // }

    sort(p+1,p+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        int a=p[i].a,b=p[i].b,id=p[i].id;
        if(c[a])c[a]--,ans[id]=a;
        else c[b]--,ans[id]=b;
        if(c[b]<0){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES\n";
    for(int i=1;i<=n;i++){
        cout<<ds[ans[i]]<<endl;
    }
}
/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/