[已解决]一道C++实验题(线段树使用)

1248762042

题目简单来说就是 第一行输入  请求数量 (n)    区间大小(size)

接下来有n行输入  每行有个起始时间 和 结束时间
先到先得, 如果这段时间被先前的请求占用了 就拒绝 否则接受
我感觉这题就是 判断 这一条线段  是否有被占用
我自己拿数组写了 发现时间复杂度太大了 可能会超时

不知道有没有大佬 可以帮忙用线段树写一下

最佳答案

月排行榜 / 总排行榜

人造人

2021-10-24 18:03:23

1248762042 发表于 2021-10-24 23:33
他就是不给测试数据的

我就讨厌这样的刷题网站，用于判断的那个程序完全知道 输入数据、正确答案、你程序给出的答案
但是这个程序是这样说的，你写的这个程序不对，至于有什么问题，我不告诉你，你自己去看代码，改代码
一个好的刷题网站应该是这样的
你的这个程序不正确，在输入 1234 的时候，正确的输出应该是 1，但是你提供的程序输出的是 0
你看这样不好吗？有了输入数据、正确答案、错误答案，可以非常快速的定位代码中存在的问题
对于前面的那个刷题网站，他不告诉我这 3 个数据，我只能一行代码一行代码的找问题，想了又想，是哪里漏掉了某种情况？
我非常非常讨厌这样的刷题网站，因为代码出现问题根本没法修改代码，因为不知道这 3 个数据，输入数据、正确答案、错误答案


好了，下面说正事
再试一下这个代码，这次用了 线段树（大概，^_^）
segment_tree.hpp

#ifndef _SEGMENT_TREE_HPP_
#define _SEGMENT_TREE_HPP_

#include <cstddef>

template <typename T>
class segment_tree_t {
public:
    segment_tree_t(size_t begin, size_t end, T value = T()): root(nullptr) {
        if(begin > end) return;
        root = create(begin, end, value);
    }
    ~segment_tree_t() {
        free(root);
    }
    bool get(size_t begin, size_t end, long long &sum) {
        if(!root) return false;
        if(begin > end) return false;
        sum = get_sub(root, begin, end);
        return true;
    }
    bool set(size_t begin, size_t end, T value) {
        if(!root) return false;
        if(begin > end) return false;
        set_sub(root, begin, end, value);
        return true;
    }
private:
    struct node_t {
        size_t begin, end;
        T value;
        node_t *lchrild, *rchrild;
    };
    node_t *root;
    static node_t *create(size_t begin, size_t end, T value) {
        node_t *root = new node_t();
        root->begin = begin;
        root->end = end;
        if(begin == end) {
            root->lchrild = root->rchrild = nullptr;
            root->value = value;
            return root;
        }
        size_t middle = (begin + end) / 2;
        root->lchrild = create(begin, middle, value);
        root->rchrild = create(middle + 1, end, value);
        root->value = root->lchrild->value + root->rchrild->value;
        return root;
    }
    static void free(node_t *root) {
        if(!root) return;
        free(root->lchrild);
        free(root->rchrild);
        delete root;
    }
    static long long get_sub(node_t *root, size_t begin, size_t end) {
        if(root->begin > end || root->end < begin) return 0;
        if(root->begin >= begin && root->end <= end) return root->value;
        return get_sub(root->lchrild, begin, end) + get_sub(root->rchrild, begin, end);
    }
    static void set_sub(node_t *root, size_t begin, size_t end, T value) {
        if(root->begin > end || root->end < begin) return;
        if(root->begin == root->end) {root->value = value; return;}
        set_sub(root->lchrild, begin, end, value);
        set_sub(root->rchrild, begin, end, value);
        root->value = root->lchrild->value + root->rchrild->value;
    }
    segment_tree_t(const segment_tree_t &rhs) = delete;
    segment_tree_t &operator=(const segment_tree_t &rhs) = delete;
};

#endif

main.cpp

#include <iostream>
#include "segment_tree.hpp"

int main() {
    size_t n, m; std::cin >> n >> m;
    segment_tree_t<size_t> st(1, m);
    for(size_t i = 0; i < n; ++i) {
        size_t l, r; std::cin >> l >> r;
        long long sum;
        st.get(l, r, sum);
        if(sum == 0) {
            st.set(l, r, 1);
            std::cout << "ACCEPTED" << std::endl;
        } else std::cout << "REJECTED" << std::endl;
    }
    return 0;
}

跳转到最佳答案楼层

人造人

1248762042 发表于 2021-10-24 23:33
他就是不给测试数据的

我就讨厌这样的刷题网站，用于判断的那个程序完全知道 输入数据、正确答案、你程序给出的答案
但是这个程序是这样说的，你写的这个程序不对，至于有什么问题，我不告诉你，你自己去看代码，改代码
一个好的刷题网站应该是这样的
你的这个程序不正确，在输入 1234 的时候，正确的输出应该是 1，但是你提供的程序输出的是 0
你看这样不好吗？有了输入数据、正确答案、错误答案，可以非常快速的定位代码中存在的问题
对于前面的那个刷题网站，他不告诉我这 3 个数据，我只能一行代码一行代码的找问题，想了又想，是哪里漏掉了某种情况？
我非常非常讨厌这样的刷题网站，因为代码出现问题根本没法修改代码，因为不知道这 3 个数据，输入数据、正确答案、错误答案


好了，下面说正事
再试一下这个代码，这次用了 线段树（大概，^_^）
segment_tree.hpp

#ifndef _SEGMENT_TREE_HPP_
#define _SEGMENT_TREE_HPP_

#include <cstddef>

template <typename T>
class segment_tree_t {
public:
    segment_tree_t(size_t begin, size_t end, T value = T()): root(nullptr) {
        if(begin > end) return;
        root = create(begin, end, value);
    }
    ~segment_tree_t() {
        free(root);
    }
    bool get(size_t begin, size_t end, long long &sum) {
        if(!root) return false;
        if(begin > end) return false;
        sum = get_sub(root, begin, end);
        return true;
    }
    bool set(size_t begin, size_t end, T value) {
        if(!root) return false;
        if(begin > end) return false;
        set_sub(root, begin, end, value);
        return true;
    }
private:
    struct node_t {
        size_t begin, end;
        T value;
        node_t *lchrild, *rchrild;
    };
    node_t *root;
    static node_t *create(size_t begin, size_t end, T value) {
        node_t *root = new node_t();
        root->begin = begin;
        root->end = end;
        if(begin == end) {
            root->lchrild = root->rchrild = nullptr;
            root->value = value;
            return root;
        }
        size_t middle = (begin + end) / 2;
        root->lchrild = create(begin, middle, value);
        root->rchrild = create(middle + 1, end, value);
        root->value = root->lchrild->value + root->rchrild->value;
        return root;
    }
    static void free(node_t *root) {
        if(!root) return;
        free(root->lchrild);
        free(root->rchrild);
        delete root;
    }
    static long long get_sub(node_t *root, size_t begin, size_t end) {
        if(root->begin > end || root->end < begin) return 0;
        if(root->begin >= begin && root->end <= end) return root->value;
        return get_sub(root->lchrild, begin, end) + get_sub(root->rchrild, begin, end);
    }
    static void set_sub(node_t *root, size_t begin, size_t end, T value) {
        if(root->begin > end || root->end < begin) return;
        if(root->begin == root->end) {root->value = value; return;}
        set_sub(root->lchrild, begin, end, value);
        set_sub(root->rchrild, begin, end, value);
        root->value = root->lchrild->value + root->rchrild->value;
    }
    segment_tree_t(const segment_tree_t &rhs) = delete;
    segment_tree_t &operator=(const segment_tree_t &rhs) = delete;
};

#endif

main.cpp

#include <iostream>
#include "segment_tree.hpp"

int main() {
    size_t n, m; std::cin >> n >> m;
    segment_tree_t<size_t> st(1, m);
    for(size_t i = 0; i < n; ++i) {
        size_t l, r; std::cin >> l >> r;
        long long sum;
        st.get(l, r, sum);
        if(sum == 0) {
            st.set(l, r, 1);
            std::cout << "ACCEPTED" << std::endl;
        } else std::cout << "REJECTED" << std::endl;
    }
    return 0;
}

人造人

不知道这样行不行

#include <iostream>
#include <vector>

bool submit(std::vector<bool> &v, size_t begin, size_t end) {
    if(begin >= end) return false;
    if(v.size() < end) return false;
    for(size_t i = begin; i < end; ++i) {
        if(!v[i]) return false;
    }
    for(size_t i = begin; i < end; ++i) {
        v[i] = false;
    }
    return true;
}

int main() {
    size_t n, m; std::cin >> n >> m;
    std::vector<bool> v(m, true);
    for(size_t i = 0; i < n; ++i) {
        size_t l, r; std::cin >> l >> r;
        if(submit(v, l - 1, r)) std::cout << "ACCEPTED" << std::endl;
        else std::cout << "REJECTED" << std::endl;
    }
    return 0;
}

1248762042

人造人 发表于 2021-10-24 19:30
不知道这样行不行

答案是对的, 但这个就是像我先前写的暴力查找,测试数据里面有百万级别的,很可能超时, 我们老师说让我们拿线段树试试

人造人

1248762042 发表于 2021-10-24 20:16
答案是对的, 但这个就是像我先前写的暴力查找,测试数据里面有百万级别的,很可能超时, 我们老师说让我们拿 ...

那我研究研究 线段树

2736946915

扫了一眼，推荐使用map映射，哈希算法的值不会随着数据增加而变长，

人造人

我看了半天线段树，没有看出线段树比我这个程序有什么优势，你发一下题目的链接，我去看一下是哪一个输入数据导致了我的程序超时的

人造人

嗯，我好像是有点理解了，但是你还是发一下链接吧

1248762042

人造人 发表于 2021-10-24 23:10
嗯，我好像是有点理解了，但是你还是发一下链接吧

他就是不给测试数据的

人造人

1248762042 发表于 2021-10-24 23:33
他就是不给测试数据的

换一个刷题网站吧，这样的刷题网站，代码出现问题没法改，真的没法改，你只能是盯着代码一行一行的看，看哪里漏掉了某种情况，这是非常痛苦的一件事
但是有了那 3 个数据，可以非常快速的定位代码中的问题

人造人

main.cpp 改一下吧，改成这样

#include <iostream>
#include "segment_tree.hpp"

int main() {
    size_t n, m; std::cin >> n >> m;
    segment_tree_t<size_t> st(1, m);
    for(size_t i = 0; i < n; ++i) {
        size_t l, r; std::cin >> l >> r;
        long long sum;
        if(st.get(l, r, sum) && sum == 0) {
            st.set(l, r, 1);
            std::cout << "ACCEPTED" << std::endl;
        } else std::cout << "REJECTED" << std::endl;
    }
    return 0;
}

1248762042

人造人 发表于 2021-10-25 10:49
main.cpp 改一下吧，改成这样

感谢大佬 我也搞清楚了