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

1248762042 · 发表于 2021-10-24 18:03:22

题目简单来说就是第一行输入  请求数量 (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;
}

复制代码

跳转到最佳答案楼层

人造人 · 发表于 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;
}

复制代码

人造人 · 发表于 2021-10-24 19:30:07

不知道这样行不行

#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 20:16:24

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

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

人造人 · 发表于 2021-10-24 20:23:10

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

那我研究研究线段树

2736946915 · 发表于 2021-10-24 22:09:28

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

人造人 · 发表于 2021-10-24 23:04:23

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

人造人 · 发表于 2021-10-24 23:10:19

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

1248762042 · 发表于 2021-10-24 23:33:01

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

他就是不给测试数据的

人造人 · 发表于 2021-10-25 10:46:47

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

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

人造人 · 发表于 2021-10-25 10:49:14

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-27 22:29:14

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

感谢大佬我也搞清楚了

账号		自动登录	找回密码
密码			立即注册