[codeforces 1430D] String Deletion

题目：1430D
题意：
给定一个由0和1组成的字符串，每次你必须执行如下两步操作：
1.选择一个位置i并且删除这个位置上面的字符
2.由相同字符组成的最大长度的连续前缀会被删除
要求最大化操作次数

思路：
题目要求我们最大化操作次数，不难发现：
当由相同字符组成的前缀的长度>=2的时候，不管选不选它，这段前缀都会被删除；
而如果不选择它，我们就需要删除后面的一个字符，这样的话可能会减少操作次数。
因此我们应该贪心地选择它，以便增多操作次数。
当由相同字符组成的前缀的长度为1，即开头不出现连续字符的时候，我们应该从最前面的有至少两个相同字符组成的块中删除一个字符。
否则，我们的操作次数可能就会变少。

当字符串全部是左右不相同的字符组成的时候，比如10101010，我们可以确定删除的次数必定是[n/2]

我们可以给每一段由相同字符组成的字符子串打上标记，
比如1110010110
标记为0001123445
使用队列储存，以方便确认最前面的数据。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int cur = 0,ans = 0,deleted = 0;
        queue<int> q;
        for(int i = 0; i < s.size(); i++)
        {
            if(i>0&&s[i]!=s[i-1])
                cur++;
            if(i>0&&s[i]==s[i-1])
                q.push(cur);
        }
        for(int i = 0; i < n; i++)
        {
            if(q.empty())
                break;
            q.pop();
            deleted++;
            ans++;
            while(!q.empty()&&i==q.front())
            {
                q.pop();
                deleted++;

            }
            deleted++;
        }
        ans += (n - deleted + 1) /2;
        cout << ans << endl;
    }
    return 0;
}