[POI2013]Usuwanka

题目大意：

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

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

保证方案存在。

思路：

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

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

源代码：

#include
    
     #include
     
      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;}