題目鏈接：點(diǎn)擊查看

題目大意：現(xiàn)在有6種T恤的型號(hào)，分別是S、M、L、XL、XXL、XXXL，現(xiàn)在給出六種型號(hào)的數(shù)量，再給出n個(gè)人可以接受的型號(hào)，每個(gè)人可以只接受一種型號(hào)，也可以接受相鄰兩種型號(hào)中的其中一種，現(xiàn)在問(wèn)能否讓所有的人都獲得屬于自己要求的衣服，可以的話輸出方案數(shù)

題目分析：一開(kāi)始讀完題目后的第一反應(yīng)是二分圖多重匹配，想都沒(méi)多想直接開(kāi)寫了，因?yàn)閷?shí)在是懶得動(dòng)腦子了，二分圖的話建完邊就可以直接跑匈牙利了，但是題目給的n達(dá)到了1e5的級(jí)別，果不其然的T掉了，于是只能換思路，因?yàn)槊總€(gè)人的T恤大小都是相鄰的，就試著去貪心，具體的貪心策略是先讓只能選擇一個(gè)型號(hào)的人優(yōu)先匹配，讓有兩個(gè)型號(hào)的人按照型號(hào)從小到大排序，然后優(yōu)先匹配小型號(hào)，其次匹配大型號(hào)，其實(shí)同理，從大到小排序也是可以貪心的，這樣一直模擬分配的過(guò)程，若過(guò)程中有某個(gè)人無(wú)法進(jìn)行分配直接輸出NO就行了，反之如果都能完成匹配，那么直接輸出匹配結(jié)果就好了

代碼：

#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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 727D T-shirts Distribution(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。