0 s, 1 s and ? Marks

Given a string consisting of 0, 1 and ? only, change all the ? to 0/1, so that the size of the largest group is minimized. A group is a substring that contains either all zeros or all ones.

Consider the following example:

0 1 1 ? 0 1 0 ? ? ?

We can replace the question marks (?) to get

0 1 1 0 0 1 0 1 0 0

The groups are (0) (1 1) (0 0) (1) (0) (1) (0 0) and the corresponding sizes are 1, 2, 2, 1, 1, 1, 2. That means the above replacement would give us a maximum group size of 2. In fact, of all the 2⁴ possible replacements, we won't get any maximum group size that is smaller than 2.

Input 

The first line of input is an integer T ( T5000) that indicates the number of test cases. Each case is a line consisting of a string that contains 0, 1 and ? only. The length of the string will be in the range [1,1000].

Output 

For each case, output the case number first followed by the size of the minimized largest group.

Sample Input 

4
011?010???
???
000111
00000000000000

Sample Output 

Case 1: 2
Case 2: 1
Case 3: 3
Case 4: 14

---

使用討論區給的關係，事實上也可以討論出來的。

最特別的是：

*0?1*     -> *0?1*      still don't know

因此考慮單一問號的情況且前後接的不同，二分答案後，
盡可能將 '?' 歸類於前面的那個，否則只好放後面。



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int greedy(int mx, char s[], int v[], int n) {
    int i, ret = 0;
    int prev = 0;
    for(i = 0; i < n; i++) {
        if(prev > mx)   return 0;
        if(s[i] == '?') {
            if(i && i != n-1 && s[i-1] != s[i+1]) {
                if(v[i] == 1) {
                    if(prev < mx) {
                        prev++;
                        prev = 0;
                    } else {
                        prev = 1;
                    }
                } else {
                    prev = 0;
                }
                if(v[i]&1)
                    ret = max(ret, 2);
                else
                    ret = max(ret, 1);
            } else if(i && i != n-1 && s[i-1] == s[i+1]) {
                if(v[i]&1)
                    ret = max(ret, 1);
                else
                    ret = max(ret, 2);
                prev = 0;
            } else {
            }
        } else {
            if(i && s[i-1] != '?')
                prev = 0;
            prev += v[i];
        }
        ret = max(ret, prev);
    }
    return ret <= mx;
}
int main() {
    int testcase, cases = 0;
    char s[1005];
    int v[1005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s", s);
        int n = strlen(s);
        int l = 1, r = n, m;
        int ret = 1;
        int i, j, k;
        m = 0;
        for(i = 0; i < n; i++) {
            s[m] = s[i], v[m] = 1;
            while(i < n && s[i+1] == s[i])
                i++, v[m]++;
            m++;
        }
        n = m;
        /*for(i = 0; i < n; i++)
            printf("%c %d\n", s[i], v[i]);*/
        while(l <= r) {
            m = (l+r)/2;
            if(greedy(m, s, v, n))
                r = m-1, ret = m;
            else
                l = m+1;
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
 * if the digits before && after "?" is different, we can change the sequence to
 * *0?1*     -> *0?1*      still don't know
 * *0??1*    -> *0101*     ans>=1
 * *0???1*   -> *01001*    ans>=2
 * *0????1*  -> *010101*   ans>=1
 * ....
 * else if they are the same, "0" is consider here, the same to "1"
 * *0?0*     -> *010*      ans>=1
 * *0??0*    -> *0110*     ans>=2
 * *0???0*   -> *01010*    ans>=1
 * *0????0*  -> *010110*   ans>=2
*/