1 条题解

  • 0
    @ 2025-4-16 16:37:14

    反向枚举字符串,当遇到 1'1'xx 计数加一,反之 yy 计数加一。

    初始化答案为 21474836472147483647 ,当第二次及之后遇到 1'1' 时,计算答案:$ans= \mathop{\max}_{s[i]='1'} \lfloor y/(x-1) \rfloor$

    时间复杂度:O(n)O(n)

    int n;
    string str;
    
    void solve()
    {
    	cin >> n >> str;
    
    	int x = 0, y = 0, ans = 2147483647;
    	for (int i = str.size() - 1; i >= 0; i--)
    		if (str[i] == '1')
    		{
    			if (++x > 1)
    				ans = min(ans, y / (x - 1));
    		}
    		else
    			++y;
    
    	cout << ans << endl;
    }
    
    • 1

    信息

    ID
    19
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者