当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

zoj 3511 Cake Robbery(线段树)

发表于: 2014-10-13   作者:阿尔萨斯   来源:转载   浏览:
摘要: 题目链接:zoj 3511 Cake Robbery 题目大意:就是有一个N边形的蛋糕,切M刀,从中挑选一块边数最多的,保证没有两条边重叠。 解题思路:有多少个顶点即为有多少条边,所以直接按照切刀切掉点的个数排序,然后用线段树维护剩下的还有哪些点。 #include <cstdio> #include <cstring> #include <vector&

题目链接:zoj 3511 Cake Robbery

题目大意:就是有一个N边形的蛋糕,切M刀,从中挑选一块边数最多的,保证没有两条边重叠。

解题思路:有多少个顶点即为有多少条边,所以直接按照切刀切掉点的个数排序,然后用线段树维护剩下的还有哪些点。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 10005;

#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], s[maxn << 2];

inline void pushdown(int u) {
    if (s[u] == 0)
        s[lson(u)] = s[rson(u)] = 0;
}

inline void pushup(int u) {
    s[u] = s[lson(u)] + s[rson(u)];
}

void build (int u, int l, int r) {
    lc[u] = l;
    rc[u] = r;

    if (l == r) {
        s[u] = 1;
        return;
    }

    int mid = (l + r) / 2;
    build(lson(u), l, mid);
    build(rson(u), mid + 1, r);
    pushup(u);
}

void modify (int u, int l, int r) {
    if (l > r)
        return;

    if (l <= lc[u] && rc[u] <= r) {
        s[u] = 0;
        return;
    }

    pushdown(u);
    int mid = (lc[u] + rc[u]) / 2;
    if (l <= mid)
        modify(lson(u), l, r);
    if (r > mid)
        modify(rson(u), l, r);
    pushup(u);
}

int N, M;
struct Seg {
    int l, r, c;
    Seg (int l = 0, int r = 0) {
        this->l = l;
        this->r = r;
        this->c = r - l + 1;
    }
    friend bool operator < (const Seg& a, const Seg& b) {
        return a.c < b.c;
    }
};
vector<Seg> vec;

int main () {
    while (scanf("%d%d", &N, &M) == 2) {
        int l, r, ans = 0;
        build(1, 1, N);
        vec.clear();

        while (M--) {
            scanf("%d%d", &l, &r);
            if (l > r) swap(l, r);
            vec.push_back(Seg(l, r));
        }
        sort(vec.begin(), vec.end());

        for (int i = 0; i < vec.size(); i++) {
            int tmp = s[1];
            modify(1, vec[i].l + 1, vec[i].r - 1);
            ans = max(ans, tmp - s[1] + 2);
        }
        printf("%d\n", max(ans, s[1]));
    }
    return 0;
}

zoj 3511 Cake Robbery(线段树)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5235 Calculate the Func
这道题网上很多代码是错误的,由于后台数据水,他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9
定义 线段树是一种的二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应
树结构的基本思想是分割。普通二叉搜索树是按对象来进行划分,效果往往和数据结构内对象有关;而线
线段树的构造思想 线段树是一棵二叉树,树中的每一个结点表示了一个 区间[a,b]。每一个叶子节点表示
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中。下图就为一个线
一、线段树基本概念 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个
线段树(Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段
线段树 一 什么是线段树 线段树是一棵二叉树,树中的每一个结点表示了一个区间[a,b]。每一个叶子节
线段树的入门级 总结 转载于:http://blog.csdn.net/x314542916/article/details/7837276 真正的入
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号