S5來襲4/11旗艦上市金豪禮★拿現金最實在!輕忽小中風,當心變殘障睽違25天終開會 立院...
2013-08-11 22:27:36 人氣(88) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][二分greedy] 11920 - 0 s, 1 s and ? Marks

0
收藏
0
推薦


  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 24 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 ( T$ le$5000) 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
*/

119200 s1 s and ? Marksgreedy
台長:Morris
人氣(88) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][greedy] 11166 - Power Signs
此分類上一篇:[UVA] 10906 - Strange Integration

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文