题解 P3551 【[POI2013]USU-Take-out】

题目链接

Solution USU-Take-out

题目大意：给定(n)块砖，黑砖是白砖的(k)倍，每次可以拿出(k + 1)块砖，要求其中只有(1)块白砖，且相邻两块砖之间的所有砖都还没有被拿出来过，求一种可行方案

贪心、栈

---

分析：首先不考虑相邻砖之间砖没有被拿出来的限制，我们可以想到一种贪心的做法

维护一个栈，如果栈顶的(k + 1)块砖里只有(1)块白砖，弹出(k + 1)块砖，将它们的位置作为一次操作

容易发现，第一次弹的(k + 1)块砖一定是连续的，后面弹的砖虽然在栈里面连续，但在原序列中两两之间的砖都被拿掉了

所以我们只要把弹栈得到操作的顺序倒过来，就可以保证操作的合法性了

#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 100;
char str[maxn];
string ans[maxn];
int n,k,cnt,top,tot,stk[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    cin >> (str + 1);
    for(int i = 1;i <= n;i++){
        stk[++top] = i;
        cnt += (str[i] == 'c');
        if(top > k + 1)cnt -= (str[stk[top - k - 1]] == 'c');
        if(cnt == 1 && top >= k + 1){
			ostringstream tmp;
            for(int i = top - k;i <= top;i++)
                tmp << stk[i] << " ";
			ans[++tot] = tmp.str();
            cnt = 0;
            for(int i = top - k - 1;i >= max(top - k - 1 - k,1);i--)cnt += (str[stk[i]] == 'c');
            top -= k + 1;
        }
    }
    for(int i = tot;i >= 1;i--)
        cout << ans[i] << '
';
    return 0;
}