Sgu/546

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Ternary Password	★★☆☆☆	答案正确	100	2015-2-21 17:02:16	无

（AC 527）

题意

一个只有0,1,2的字符串，改动尽量少的位数，得到有n个0，m个1的字符串，求改动次数和最终结果。

题解

• 很明显的贪心，首先优先使得0变1或1变0，如果仍然没有达到要求则再考虑2。写起来条件分支比较多一点。
• 不可能的情况需要特判一下。

代码

546.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; #define si(n) scanf("%d",&n) #define dsi(n) int n;si(n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,p,n) for(int i=p;i<=n;++i) #define fd(i,n) for(int i=n;i!=0;--i) #define fdi(i,p,n) for(int i=n;i>=p;--i) int countS[3]={},maxA=0,b=0; int main() { dsi(n); dsi(a0); dsi(a1); string str;cin>>str; fi(i,0,str.size()-1) ++countS[str[i]-'0']; if(a0+a1>str.size()) { cout<<-1; return 0; } //0<->1// fi(i,0,str.size()-1) { switch(str[i]) { case '0': if(countS[0]>a0&&countS[1]<a1) { --countS[0]; ++countS[1]; str[i]='1';++b; } break; case '1': if(countS[1]>a1&&countS[0]<a0) { --countS[1]; ++countS[0]; str[i]='0';++b; } break; } } //0<->2&&1<->2// fi(i,0,str.size()-1) { switch(str[i]) { case '0': if(countS[0]>a0) { --countS[0]; str[i]='2';++b; } break; case '1': if(countS[1]>a1) { --countS[1]; str[i]='2';++b; } break; case '2': if(countS[1]<a1) { ++countS[1]; str[i]='1';++b; } else if(countS[0]<a0) { ++countS[0]; str[i]='0';++b; } break; } } cout<<b<<endl<<str; }