CF1253B - Silly Mistake(贪心+构造性算法+提高级)

2021/12/20 22:19:56

本文主要是介绍CF1253B - Silly Mistake(贪心+构造性算法+提高级),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

CF1253B - Silly Mistake(源地址自⇔CF1253B)

目录
  • CF1253B - Silly Mistake(源地址自⇔CF1253B)
    • Problem
    • tag:
    • 题意:
    • 思路:
    • AC代码1(队内赛自己):
    • AC代码2(官方思路,伪代码)
    • 错误次数

Problem

tag:

⇔贪心、⇔构造性算法、⇔提高级(*1400)

题意:

(简化版)对于给定的序列,要求将其分成满足条件的若干段,条件如下:

  • 如果在这一段中有 \(k\) ,则一定要有 \(-k\) 。

输出分段的数量及每一段的元素数量;若不能恰好分割完,输出 \(-1\) 。

思路:

(队内赛自己, \(\mathcal O (n* log_2 n)\) )寻找某一元素在此前有没有出现过,容易想到二分查找,能用二分查找的容器必然是有序的,这里选用 std::set 。分三种情况讨论:

  • 读入正数 \(x\) ——若 \(x\) 不在容器中、 \(x\) 在这一分段里尚未出现过(未被标记),则将 \(x\) 加入容器。

  • 读入负数 \(-x\) ——若 \(x\) 已在容器中,则删除 \(x\) 。

  • 其他所有情况均不满足条件。

每次容器为空时,即代表一个分段,记录并将标记数组清空。


(官方,\(\mathcal O(n)\) )优化二分查找为数组直接记录,优化标记数组为 std::map (因为涉及到多次清空操作,普通数组不能胜任该工作)即可。

使用变量 len 记录分段所含元素的数量,当其为 \(0\) 时,即代表一个分段。

AC代码1(队内赛自己):

//A WIDA Project
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n, num[1000050], x, pre;
bool Ans = true;
vector<int> ans;
set<int> s, v;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> x;
        if(x > 0) {
            if(s.find(x) == s.end() && v.find(x) == v.end()) //里面没有 && 第一次放入
                s.emplace(x), v.emplace(x);
            else
                Ans = false;
        }else {
            if(x < 0 && v.find(-x) != v.end()) //负数,里面有
                s.erase(-x);
            else
                Ans = false;
        }
        if(s.empty()) {
            v.clear();
            ans.push_back(i - pre);
            pre = i;
        }
    }
    if(Ans == false || (int)ans.size() == 0 || !s.empty()) 
        cout << "-1\n";
    else {
        cout << ans.size() << "\n";
        for(auto i : ans)
            cout << i << " ";
    }
    return 0;
}

AC代码2(官方思路,伪代码)

LL n, ans, num[MAX], x, pre, len, s[MAX];
bool Ans = true;
vector<int> ans;
map<int, int> v;

int main() {
    cin >> n;
    FOR(i, 1, n) {
        cin >> x;
        if(x > 0) {
            if(s[x] == 0 && v[x] == 0)
                s[x] ++, v[x] ++, len ++;
            else 
                Ans = false;
        }else {
            if(s[-x] == 1) 
                s[-x] --, len --;
            else 
                Ans = false;
        }
        if(len == 0) {
            v.clear();
            ans.push_back(i - pre);
            pre = i;
        }
    }
    if(Ans == false || sz(ans) == 0 || len != 0) 
        P(-1);
    else {
        P(ans.size());
        For(i, ans)
            cout << i << " ";
    }
    return 0;
}

错误次数

(补题1)忘记判断结束时容器是否为空,若有数据则也是 \(-1\) 。WA。


文 / WIDA
2021.12.20 成文
首发于WIDA个人博客,仅供学习讨论


更新日记:
2021.12.20 成文




这篇关于CF1253B - Silly Mistake(贪心+构造性算法+提高级)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程