Codeforces 727 D T-shirts Distribution

Description

有 \(6\) 种尺码的衣服,有的人只适合 \(1\) 种衣服,有的人适合相邻的 \(2\) 种,问是否存在合法方案,并输出.

Sol

贪心.

首先,只适合 \(1\) 种衣服的直接减去就好了,如果个数小于 \(0\) 了直接不合法.

然后考虑适合两种衣服的.首先就是,可以跑网络流或者二分图匹配.

一共就有 \(5\) 种情况 \((1,2),(2,3),(3,4),(4,5),(5,6)\) .

很容易的,我们就发现它其实可以贪心...

对于第 \(1\) 种情况,如果 \(1\) 号衣服有剩余的,那么就使用,然后不够就使用下一个即可.

以此类推.

排一下序,统计一下个数直接贪心就好.

Code

#include<cstdio>

#include<cstring>

#include<utility>

#include<algorithm>

#include<iostream>

using namespace std;

#define mpr(a,b) make_pair(a,b)

const int N = 100005;

int n,m,a[10],b[10];

int g[N];

pair< pair<int,int> , int>  p[N];

pair<int,int> q[10];

pair<int,int> ans;

int sum[10];

int kind(char a[]){

	if(a[0]=='S') return 1;

	if(a[0]=='M') return 2;

	if(a[0]=='L') return 3;

	if(strlen(a)==2) return 4;

	if(strlen(a)==3) return 5;

	return 6;

}

int main(){

	for(int i=1;i<=6;i++) cin>>a[i],b[i]=a[i];

	cin>>n;

//	cout<<n<<endl;

	for(int i=1;i<=n;i++){

		char ch=getchar();

		char tmp[10];int l=0;

		memset(tmp,0,sizeof(tmp));

		while(ch>'Z'||ch<'A') ch=getchar();

		while(ch>='A'&&ch<='Z') tmp[l++]=ch,ch=getchar();

		if(ch==','){

			int t1=kind(tmp),t2;

			ch=getchar(),l=0,memset(tmp,0,sizeof(tmp));

			while(ch>'Z'||ch<'A') ch=getchar();

			while(ch>='A'&&ch<='Z') tmp[l++]=ch,ch=getchar();

			t2=kind(tmp);

			if(t1>t2) swap(t1,t2);

			p[++m]=mpr(mpr(t1,t2),i);

		}else{

			a[kind(tmp)]--,b[kind(tmp)]--;g[i]=kind(tmp);

			if(a[kind(tmp)]<0){ puts("NO");return 0; }

		}

	}

	sort(p+1,p+m+1);

	for(int i=1;i<=5;i++) q[i]=mpr(i,i+1);

	for(int i=1;i<=m;i++) for(int j=1;j<=5;j++) if(p[i].first==q[j]) sum[j]++;

	for(int i=1;i<=6;i++) if(a[i]<0){ puts("NO");return 0; }

	for(int i=1;i<=5;i++){

		if(a[i]>=sum[i]) a[i]-=sum[i];

		else{

			a[i+1]-=sum[i]-a[i],a[i]=0;

		}

		for(int j=1;j<=6;j++) if(a[j]<0){ puts("NO");return 0; }

	}

	for(int i=1;i<=6;i++) if(a[i]<0){ puts("NO");return 0; }

	puts("YES");

	for(int i=1;i<=m;i++){

		for(int j=1;j<=5;j++) if(p[i].first==q[j]){

			if(b[j]>a[j]) g[p[i].second]=j,b[j]--;

			else g[p[i].second]=j+1,b[j+1]--;

		}

	}

	for(int i=1;i<=n;i++){

		switch(g[i]){

			case 1:puts("S");break;

			case 2:puts("M");break;

			case 3:puts("L");break;

			case 4:puts("XL");break;

			case 5:puts("XXL");break;

			case 6:puts("XXXL");break;

		}

	}

	return 0;

}