20200309(ABC)题解 by 梁延杰

今日题解:
A :先考虑n=1 的情况 题目说每个人都要至少分一包,所以果断-1
再考虑n=2的情况 如果两包不相同就随便输出一包和编号,否则是-1
由于要分两组不一样,所以只要其中一个人只给他最小值,那么这两组一定不相同(因为几个比最小值大的数加起来一定大于最小值而不等于最小值)所以直接输出1和最小值编号即可。

B:题目给定了的输入是奇数和偶数相同的序列,这样这题就简单了很多。用一个cnt来记录当前的情况,是奇数就+1 是偶数就-1 当cnt等于0 的时候 说明前面的已经是奇偶相同了,因为题目给的是奇数和偶数相同的序列,所以一旦前面的满足奇偶相同了,后面也一定满足。这时候把id给记录下来放到一个数组里排序,每次如果能分割的话ans++,用m减到不能减,最后能分割的就是最多的次数。

C:如果全是1 直接输出0
统计一下n0n1这样的子串的数量,比如 01  001 0001 0011 具体方法是s[i]=='1' && s[i-1]=='0',这样的都可以把1全都挪到后面。统计完数量之后如果最后一位是0的话cnt++ 因为这样的是没统计的。最后枚举一下最小的x*i+(cnt-i)*y(把带1的子串放到后面的次数*x+转换0到1的次数*y)cnt-1次就可以把1全都移动到后面,因为第cnt个带1的已经在该在的位置了,而最后一位是0的话也是cnt-1 ,因为还需要把第cnt-1个移到后面。

原文地址:https://www.cnblogs.com/QLU-ACM/p/12482629.html