鸭子唱歌-贪心

题目描述

小明的楼下出现了许多鸭子，一开始只有一只鸭子在唱歌，“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 3quackquakc -1quackquack 1 */

总结

以上是生活随笔为你收集整理的鸭子唱歌-贪心的全部内容，希望文章能够帮你解决所遇到的问题。

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