CodeForces-1680C Binary String

Binary String

二分 + 尺取 || 尺取

二分+尺取：时间复杂度为 \(O(nlogn)\)

答案是单调的，所以直接二分枚举答案，然后再 judge 判断的时候，尺取中间剩下的区间

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define pii pair
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
string s;
int sum = 0;

int query(int x)
{
    int l = 0, r = 0, len = s.length(), cnt0 = 0, cnt1 = 0;
    while(l < len)
    {
        while(r < len && cnt0 <= x)
        {
            if(s[r] == '0') cnt0++;
            else cnt1++;
            r++;
        }
        if(sum - cnt1 <= x) return true;
        if(s[l] == '1') cnt1--;
        else cnt0--;
        l++;
    }
    return max(cnt0, sum - cnt1) <= x;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> s;
        int l = 0, r = s.length();
        sum = 0;
        for(int i=0; i> 1;
            if(query(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }

    return 0;
}

尺取，时间复杂度为 \(O(n)\)

这里用到一个贪心，只有在剩余区间的代价和删除区间的代价尽可能相等的时候，是最优解

所以就可以根据这个，尺取每个区间 \([l, r]\)，因为对于区间 \([l_{i+1}, r_{i+1}]\)，必然有 \(r_i \leq r_{i+1}\)

#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int cnt0 = 0, cnt1 = 0, len = s.length();
        for(int i=0; i
二分

相关

牛客练习赛91（并查集+二维偏序+二分）

数据结构与算法之PHP查找算法（二分查找）

二分查找模板（准确找定值）

浅谈二分的边界问题

算法之二分法

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

leetcode-二分查找相关

二分查找算法细节详解

c_mt_找有k个数小于自己的数（二分->复杂化 / 排序简化）

二分搜索的变形

leetcode154. 寻找旋转排序数组中的最小值 II（二分）

二分查找

标签