PID597 / 教主的别墅
题目描述

【题目背景】

  LHX教主身为宇宙第一富翁,拥有一栋富丽堂皇的别墅,由于别墅实在太大了,于是教主雇佣了许许多多的人来负责别墅的卫生工作,我们不妨称这些人为LHXee。

【题目描述】

  教主一共雇佣了N个LHXee,这些LHXee有男有女。

  教主的大别墅一共有M个房间,现在所有的LHXee在教主面前排成了一排。教主要把N个LHXee分成恰好M个部分,每个部分在队列中都是连续的一段,然后分别去打扫M个房间。

  教主身为全世界知识最渊博的人,他当然知道男女搭配干活不累的道理,以及狼多羊少,羊多狼少的危害之大。所以教主希望一个分配方式,使得所有小组男女个数差的最大值最小。

教主还希望你输出从左到右,每个组的人数。

  如果有多种人数组合都能达到最优值,教主希望你分别告诉他这些方案中字典序最小和最大的方案。换句话说,你需要找到两种方案,这两种方案满足所有组男女个数差最大值最小的前提下,第一种方案(字典序最小)要越靠前的组人数越少,也就是让第一个小组人尽量少,并且在第一个小组人尽量少的前提下,让第二个小组的人尽量少,依此类推;第二种方案(字典序最大)则要让越靠前的组人数越多。

【数据规模】

对于40%的数据,有N ≤ 100;

对于50%的数据,有N ≤ 1000;

对于65%的数据,有N ≤ 100000;

对于100%的数据,有N ≤ 5000000,M ≤ N且M ≤ 100000。

【提示】

关于字典序:

比较S1[N]与S2[N]的字典序大小,可以找到S1[N]与S2[N]中第1个不相同数字S1[i]与S2[i](即有对于所有1≤k<i,都有S1[k] =S2[k],但S1[i]≠S2[i])。如果S1[i]<S2[i],那么说S1[N]字典序比S2[N]小,否则说S1[N]字典序比S2[N]大。

输入格式

输入的第1行为两个正整数N与M,用空格分隔。

  第2行包含一个长度为N的串,仅由字符组成,第i 个字符为0表示在这个位置上的LHXee为女生,若为1则为男生。

输出格式

输出文件包含两行,每行M个正整数,正整数之间用空格隔开,行末无多余空格。这M个正整数从左到右描述了你所分的每个组的人数。

第1行为字典序最小的方案,第2行为字典序最大的方案。

【样例说明】

字典序最小的方案按1, 10, 01100分组,每组男女个数差的最大值为1,为最小。

字典序最大的方案按11001, 10, 0分组。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论