[POI2013]Usuwanka

题目大意：

一排\(n\)个球，有黑白两种颜色。每取走一个球会在原位置放一个水晶球。求构造一种取球方案，满足：

1. 每次取走\(k\)个白球和\(1\)个黑球；
2. 一次取走的任意两个球之间没有水晶球。

保证方案存在。

思路：

用栈维护黑球的出现次数，若栈顶\(k+1\)个数中恰好有\(1\)个黑球，说明这些球可以一次性取出。

时间复杂度\(\mathcal O(n)\)。

源代码：

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

inline bool getval() {

	register char ch;

	while(!isalpha(ch=getchar()));

	return ch=='c';

}

const int N=1e6+1;

int sum[N],ans[N],stk[N];

int main() {

	const int n=getint(),k=getint();

	for(register int i=1;i<=n;i++) {

		stk[++stk[0]]=i;

		sum[stk[0]]=sum[stk[0]-1]+getval();

		if(stk[0]>=k+1&&sum[stk[0]]-sum[stk[0]-k-1]==1) {

			for(register int i=0;i<=k;i++) {

				ans[++ans[0]]=stk[stk[0]--];

			}

		}

	}

	for(register int i=n;i>=1;i--) {

		printf("%d%c",ans[i]," \n"[i%(k+1)==1]);

	}

	return 0;

}