[数据结构与算法]C. Penalty

C. Penalty

Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)

题目大意:

从1开始，奇数球第一队踢；偶数，第二队踢球，

每个球有三种情况：

如果是’1’，肯定踢进
如果是’0’，肯定踢不进
如果是’?’，可以是进也可以不进

问最少踢多少球就可以判断输赢

题解：
答案肯定从6开始，（此时假设第一队获胜3局，第二队获胜0局已经进行了三局，最多还能获胜2局，必输）

从6枚举到10，每一次如果可以判定: A队获胜次数 > B队最多的获胜次数

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
int main()
{
    int n; 
    cin >> n;
    while(n--)
    {
        char g[20];

        for (i = 1; i<= 10; i++) cin >> g[i];

        int res = 0;

        for (int i=6; i<=10;i++)
        {
            int x1=0,x0=0,x3=0;
            int y1=0,y0=0,y3=0;
            for(int j=1;j<=i;j++){
                if(i&1){
                    if(g[i]=='1') x1++;
                    if(g[i]=='0') x0++;
                    if(g[i]=='?') x3++;
                }else{    
                    if(g[i]=='1') y1++;
                    if(g[i]=='0') y0++;
                    if(g[i]=='?') y3++;
                }
            }
            int x_1_1 = x1+x3;
            int x_1_0 = x0+x3;
            int x_2_1 = y1+y3; 
            int x_2_0 = y0+y3
            if(5-x_1_0 < x_2_1 || 5-x_2_0 < x_1_1)
            {
                res = i;
                break;
            }
        }
        if(res==0) cout << 10 << endl;
        else cout << res << endl;
    }
    return 0;
}