CodeForces - 727D T-shirts Distribution(贪心)

题目链接：点击查看

题目大意：现在有6种T恤的型号，分别是S、M、L、XL、XXL、XXXL，现在给出六种型号的数量，再给出n个人可以接受的型号，每个人可以只接受一种型号，也可以接受相邻两种型号中的其中一种，现在问能否让所有的人都获得属于自己要求的衣服，可以的话输出方案数

题目分析：一开始读完题目后的第一反应是二分图多重匹配，想都没多想直接开写了，因为实在是懒得动脑子了，二分图的话建完边就可以直接跑匈牙利了，但是题目给的n达到了1e5的级别，果不其然的T掉了，于是只能换思路，因为每个人的T恤大小都是相邻的，就试着去贪心，具体的贪心策略是先让只能选择一个型号的人优先匹配，让有两个型号的人按照型号从小到大排序，然后优先匹配小型号，其次匹配大型号，其实同理，从大到小排序也是可以贪心的，这样一直模拟分配的过程，若过程中有某个人无法进行分配直接输出NO就行了，反之如果都能完成匹配，那么直接输出匹配结果就好了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n;const string str[]={"S","M","L","XL","XXL","XXXL"};int ans[N],num[10];struct Node {int id,a,b;Node(int ID,int A,int B){id=ID;a=A;b=B;}bool operator<(const Node& t)const{return a<t.a;} };vector<Node>v;bool solve() {scanf("%d",&n);for(int i=1;i<=n;i++){string s;cin>>s;if(s.find(",")!=string::npos){string a=s.substr(0,s.find(","));string b=s.substr(s.find(",")+1);for(int j=0;j<6;j++){if(str[j]==a){v.push_back(Node(i,j,j+1));break;}}}else{for(int j=0;j<6;j++){if(s==str[j]){if(num[j]==0)return false;num[j]--;ans[i]=j;}}}}sort(v.begin(),v.end());for(int i=0;i<v.size();i++){if(num[v[i].a]){num[v[i].a]--;ans[v[i].id]=v[i].a;}else if(num[v[i].b]){num[v[i].b]--;ans[v[i].id]=v[i].b;}elsereturn false;}return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);for(int i=0;i<6;i++)scanf("%d",num+i);if(solve()){puts("YES");for(int i=1;i<=n;i++)puts(str[ans[i]].c_str());}elseputs("NO");return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 727D T-shirts Distribution(贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。