字符串消除-庞果网题目
题目链接：http://hero.pongo.cn/Question/Details?ID=85&ExamID=83
解决方法：贪心法
详细描述：每次从字符串选择两个相邻可消除字符，要求是这两个字符都是当前最多和次多的。例如abbcabca，a和b各有三个，而c只有两个。就先消除ab，转成c。只转一个字符，然后重新统计整个字符串cbcabca，c有三个，而a和b都是两个，但是先搜到cb，所以转cb为a。
原理证明：要求最终生成的字符串最短，肯定是被消除的次数最多，而且最终生成的字符串肯定只有一种字符。要达到最终消除次数最多，每次消除当前最多的字符，最好同时消除次多的字符，避免出现多个相同字符连续的情况，即可。假设不消除最多的，那么可能出现生成生成更多的最多字符，从而最终不能消除。
具体实现（已提交通过）：
#include <cstdio>#include <cstdio>#include <string>#include <cstring>#include <ctime>#include <cstdlib>using namespace std;int max(int a,int b,int c){ int max = 0; if(a>b) { max = a; } else { max = b; } if(max<c) { max = c; } return max;}char clearCh(char a,char b){ if(a==b) { return a; } if((a == 'a' && b == 'b') || (a == 'b' && b == 'a')) { return 'c'; } if((a == 'b' && b == 'c') || (a == 'c' && b == 'b')) { return 'a'; } if((a == 'a' && b == 'c') || (a == 'c' && b == 'a')) { return 'b'; } return a;}void clearFirst(const char *s,char *p,char a,char b){ int i=0; int clearFlag = 0; for(i=0;i<strlen(s)-1;i++) { if((s[i]==a && s[i+1]==b)||(s[i]==b && s[i+1]==a)) { strncpy(p,s,i); *(p+i) = clearCh(a,b); strncpy(p+i+1,s+i+2,strlen(s)-i-2); clearFlag = 1; break; } } if(clearFlag == 0) { for(i=0;i<strlen(s)-1;i++) { if((s[i]==a && s[i+1]!=a)||(s[i]!=a && s[i+1]==a)) { strncpy(p,s,i); *(p+i) = clearCh(s[i],s[i+1]); strncpy(p+i+1,s+i+2,strlen(s)-i-2); clearFlag = 1; break; } } } //printf("%s\n",p);}int minLength(const char *s) { int a=0,b=0,c=0,i=0,minLen=0; for(i=0;i<strlen(s);i++) { if(s[i] == 'a') { a++; } if(s[i] == 'b') { b++; } if(s[i] == 'c') { c++; } } if(a == 0 && b == 0) { minLen = c; } else if(b == 0 && c == 0) { minLen = a; } else if(a == 0 && c == 0) { minLen = b; } else { char *p = new char[strlen(s)]; if(p==NULL) { return -1; } memset(p,0,sizeof(char)*(strlen(s))); if(a>=b && b>=c) { clearFirst(s,p,'a','b'); } else if(a>=c && c>=b) { clearFirst(s,p,'a','c'); } else if(b>=a && a>=c) { clearFirst(s,p,'b','a'); } else if(b>=c && c>=a) { clearFirst(s,p,'b','c'); } else if(c>=b && b>=a) { clearFirst(s,p,'c','b'); } else if(c>=a && a>=b) { clearFirst(s,p,'c','a'); } minLen = minLength(p); delete(p); } return minLen;}//start 提示：自动阅卷起始唯一标识，请勿删除或增加。int main(){ return 0;} //end //提示：自动阅卷结束唯一标识，请勿删除或增加。