题目描述
小明的楼下出现了许多鸭子，一开始只有一只鸭子在唱歌，“quack……quack……quack……”，小明觉得还挺好听的。紧接着，所有鸭子都一起唱了起来。小明开始厌烦了，他想要知道到底有多少只鸭子在他家楼下。
由于鸭子们边唱边跳，小明数着数着就数不清楚了。因此他想到了一个办法，把鸭子的声音录下来，用计算机来进行分析。一只鸭子发出的声音，只能是“quack”唱完整的一遍或者连续多遍，但是不同鸭子的声音会叠加，同一个微小的时刻就只有1只鸭子发出一个声音。例如：“ququaackck”就是由两只鸭子的声音叠加而成的，第一只是“qu___ack”,第二只是“__qua___ck”；又例如，“quackquack”这段声音，可能是1只鸭子，也可能是2只鸭子发出的。如果小明获取的声音是类似“quakc”不是由“quack”重复构成，或者只是其中一部分，这样的声音就是不规则，无效的。
现在，小明记录下了一段时间内鸭子的声音，问，这段声音中最少包含多少只鸭子？
输入
输入只有一行，一个字符串表示鸭子的声音。字符串中只包含“q”，“u”，“a”，“c”，“k”这5种小写字母。
输出
输出最少包含鸭子数量。若小明的声音录制无效，输出-1。
样例输入
【样例1】
quqacukqauackck
【样例2】
quackquakc
【样例3】
qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk
样例输出
【样例1】
2
【样例2】
-1
【样例3】
10
提示
样例1解释
鸭子1：qu_ac_kq_uack__
鸭子2：__q__u__a____ck
声音最少由2只鸭子构成，第一只鸭子唱了2遍，第二只鸭子唱了一遍。
样例2解释
不规则序列，不能由“quack”构成
数据范围
30%的数据，鸭子的声音长度不超过200
70%的数据，鸭子的声音长度不超过1000
100%的数据，鸭子的声音长度不超过2500
tag:瞎贪心
要找到最小的鸭子数量，首先可以考虑贪心一下
贪心策略：
- 首先将不符合条件的情况给特判掉：
长度 % 5 ！= 0应该直接输出-1
并且还要使得三种字符的数量保持相等才可以
- 剩下的策略：要有一只鸭子尽可能多的发出quack 来才是最优的，所以说我们在选择字符的过程中，选择里该字符最近的下一个字符，这样后面的字符就会尽可能靠前，当一个完整的单词出现过之后，再次选择第一个字母q 的时候，要尽可能选择之前k 后面的q，这样会使得鸭子的数量尽可能少，答案就不用+1，但是没有办法找到k后面的q的情况下，就应该选择最前面的q，这样一来，对答案的贡献+1
- 还有以下小细节，比如说在最后一轮中发现了最后的k在c前面，那就是不合法的情况，如果最终所有的字母仍有剩余，就是-1的情况
Code:(又臭又长，可以换种方法 模拟一下)
int n,m,k; ll ans; string s; int b[maxn]; map<char,int> mp; set<int> stq,stu,sta,stc,stk; int judge(){ int sum = stq.size()+stu.size()+sta.size()+stc.size()+stk.size(); return sum; } int main() { cin >> s; int len = s.size(); s = " " + s; if(len % 5) { puts("-1"); return 0; } int aver = len / 5; for(int i=1; i<=len; i++) { if(s[i] == 'q') stq.insert(i); else if(s[i] == 'u') stu.insert(i); else if(s[i] == 'a') sta.insert(i); else if(s[i] == 'c') stc.insert(i); else if(s[i] == 'k') stk.insert(i); } if(stq.size() != aver || stu.size() != aver || sta.size() != aver || stc.size() != aver || stk.size() != aver){ puts("-1"); return 0; } int cnt = 1; int pre = 0; int q,u,a,c; while(stq.size()){ if(*stq.rbegin() < pre) q = *stq.begin(),stq.erase(stq.begin()),cnt++; else q = *stq.lower_bound(pre),stq.erase(stq.lower_bound(pre)); //if(q < pre) cnt ++; if(*stu.rbegin() < q){ puts("-1"); return 0; } u = *stu.lower_bound(q); stu.erase(stu.lower_bound(q)); // printf("u: %d \n",u); if(*sta.rbegin() < u){ puts("-1"); return 0; } a = *sta.lower_bound(u); sta.erase(sta.lower_bound(u)); // printf("a: %d \n",a); if(*stc.rbegin() < a){ puts("-1"); return 0; } c = *(stc.lower_bound(a)); stc.erase(stc.lower_bound(a)); // printf("c: %d \n",c); if(*stk.rbegin() < c){ puts("-1"); return 0; } pre = *(stk.lower_bound(c)); stk.erase(stk.lower_bound(c)); // printf("%d %d %d %d %d\n",q,u,a,c,pre); } if(judge()) puts("-1"); else cout << cnt <<endl; return 0; } /* qqquuuaaaccckkk 3 quackquakc -1 quackquack 1 */
