[POI 20 Stage 1] Take-out

作法：

直接決定拿法太困難了，因為根本沒辦法掌握拿完第一次之後中間剩下的空隙們到底有沒有辦法被拿完。如果考律把整個拿的過程倒過來的話，整個算法大概會變成：每次找一段連續的符合條件的區間，把它們全部拿光，然後把剩下的左右兩堆接起來繼續拿，直到拿光為止，不難發現這樣拿完之後把整個拿的過程倒過來就會得到所求的合法的拿法。

實作上可以直接用一個 stack ，每次加進一個東西進 stack ，如果頂端的 k+1 個數滿足條件了就把它們全部拿出來。至於怎麼判斷頂端的 k+1 個數是否滿足條件，只要再多維護一個 stack 中元素的前綴和陣列就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int st[maxn],sum[maxn] ;
char s[maxn] ;
vector<int> v[maxn] ;
 
int S(int x,int y)
{
    return x ? sum[y]-sum[x-1] : sum[y] ;
}
 
main()
{
    int n,k ; scanf("%d%d%s",&n,&k,s+1) ;
    int sz=0 , now=1 ;
    for(int i=1;i<=n;i++)
    {
        st[sz]=i ;
        if(s[i]=='c') sum[sz]=(sz ? sum[sz-1] : 0) + 1 ;
        else sum[sz]= ( sz ? sum[sz-1] : 0 ) ;
        sz++ ;
        if(sz>=k+1 && S(sz-k-1,sz-1)==1)
        {
            for(int j=sz-k-1;j<=sz-1;j++) v[now].push_back(st[j]) ;
            sz-=k+1 ;
            now++ ;
        }
    }
    for(int i=n/(k+1);i>=1;i--)
        for(int j=0;j<v[i].size();j++)
            printf("%d%c",v[i][j],j+1==v[i].size()?'\n':' ') ;
}