A: 2020(贪心+二分)

2020

https://ac.nowcoder.com/acm/contest/7502/A

参考blog:https://blog.csdn.net/qq_43814654/article/details/109407083
题意:找出一个字符串中能组成2020串的最大值
分析:
1.在寻找的时候可以找到很多的20对。但是当出现222000这种情况的时候,虽然有3个20对,但是无法组成2020。但是222000222000的时候就可以组成3组2020。我们发现,要尽可能多的组成2020,可以尽可能让前面的20对作为2020的前半部分,之后的20对再和之前组成的形成2020对。
2.直接寻找答案的话,不是很好寻找,因为不知道你统计了多少个前面20对后,应该开始统计后面的20对。所以采取二分的方式来寻找最终的答案。
3.判断是否能组成x个2020.先统计x个开始的20串,这时候要保证0的个数小于等于2的个数,才能保证0的前面都有
2.当前面20的2的个数收集满的时候,就可以收集后面20的2.但是后面的2的个数要保证小于前面20中0的个数。因为如果大于的话,说明前面有一些20串缺少0,如果你计入的话,就会出现22的情况。最后就要保证后面20的0小于后面20的2的个数
4.最后记得判断l是false的话,要--l(因为是l+1 = r)才导致跳出循环的

代码块
ac code:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define ll long long
#ifdef ONLINE_JUDGE
#else
#define scanf scanf_s
#endif // ONLINE_JUDGE
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define ROF(i,a,b) for(int i = a;i >= b;i--)
ll read() {
    ll X = 0, w = 1; char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}
ll poww(ll a, ll b, ll mod) {
    ll base = 1;
    while (b) {
        if (b & 1) { base = base * a % mod; }
        b >>= 1; a = a * a % mod;
    }
    return base;
}
int  n;
string s;

bool fun(int mid) {
    int a1 = mid, b1 = 0, a2 = 0, b2 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')continue;
        if (s[i] == '2') {
            if (a1)--a1, ++b1;
            else if (a2) --a2, ++b2;
        } 
        else if (s[i] == '0') {
            if (b1) --b1,++a2;
            else if (b2) --b2;
        }
    }
    if (!a1 && !a2 && !b1 && !b2) return true;
    return false;
}
int main() {
    while (cin >> n >> s) {
        int l, r, mid;
        l = 0, r = n / 4;
        while (l < r) {
            mid = (l + r) >> 1;
            if (fun(mid)) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        if (!fun(l)) --l;
        cout << l << endl;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
2022-12-14 18:10
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议