首页 > 代码库 > Codeforces 727 D T-shirts Distribution
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;}
Codeforces 727 D T-shirts Distribution
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。