[贪心]教主的别墅

本文主要是介绍[贪心]教主的别墅，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
教主一共雇佣了N个LHXee，这些LHXee有男有女。
　　教主的大别墅一共有M个房间，现在所有的LHXee在教主面前排成了一排。教主要把N个LHXee分成恰好M个部分，每个部分在队列中都是连续的一段，然后分别去打扫M个房间。
　　教主身为全世界知识最渊博的人，他当然知道男女搭配干活不累的道理，以及狼多羊少，羊多狼少的危害之大。所以教主希望一个分配方式，使得所有小组男女个数差的最大值最小。
　　教主还希望你输出从左到右，每个组的人数。
　　如果有多种人数组合都能达到最优值，教主希望你分别告诉他这些方案中字典序最小和最大的方案。换句话说，你需要找到两种方案，这两种方案满足所有组男女个数差最大值最小的前提下，第一种方案（字典序最小）要越靠前的组人数越少，也就是让第一个小组人尽量少，并且在第一个小组人尽量少的前提下，让第二个小组的人尽量少，依此类推；第二种方案（字典序最大）则要让越靠前的组人数越多。

Input

　　输入的第1行为两个正整数N与M，用空格分隔。
　　第2行包含一个长度为N的串，仅由字符组成，第i 个字符为0表示在这个位置上的LHXee为女生，若为1则为男生。

Output

　　输出文件包含两行，每行M个正整数，正整数之间用空格隔开，行末无多余空格。这M个正整数从左到右描述了你所分的每个组的人数。
　　第1行为字典序最小的方案，第2行为字典序最大的方案。

Sample Input

8 3
11001100

Sample Output

1 2 5
5 2 1

Data Constraint

Hint

【样例说明】
　　字典序最小的方案按1, 10, 01100分组，每组男女个数差的最大值为1，为最小。
　　字典序最大的方案按11001, 10, 0分组。

【数据规模】
　　对于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]大。

#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for (i=a;i<=b;i++)
using namespace std;
int n,m,a[5000001],s[5000001];
int i,ans,pre,p;
int fuc(int a,int b)
{return (int)abs(a-b)%p==0?0:1;
}
int main()
{scanf("%d%d\n",&n,&m);rep(i,1,n){char c;scanf("%c",&c);a[i]=c-48;if (a[i]==0) a[i]--;s[i]=s[i-1]+a[i];}if (s[n]!=0)ans=abs(s[n])/m+((int)abs(s[n])%m==0?0:1);else{int t=0;rep(i,1,n)t+=s[i]==0;if (t>=m) ans=0;else ans=1;}p=m-1;rep(i,1,n)if (s[i]-s[pre]<=ans&&abs(s[n]-s[i])/p+fuc(s[n],s[i])<=ans){printf("%d ",i-pre);pre=i;p--;if (p==0) break;}printf("%d\n",n-pre);for (i=n;i>=1;i--)s[i]=s[i+1]+a[i];if (s[1]!=0)ans=abs(s[1])/m+((int)abs(s[1])%m==0?0:1);else{int t=0;for (i=n;i>=1;i--)t+=s[i]==0;if (t>=m) ans=0;else ans=1;}p=m-1;pre=n+1;for (i=n;i>=1;i--)if (s[i]-s[pre]<=ans&&abs(s[1]-s[i])/p+fuc(s[1],s[i])<=ans){a[p+1]=pre-i;pre=i;p--;if (p==0) break;}a[1]=pre-1;rep(i,1,m)printf("%d ",a[i]);
}