首页 > 代码库 > ZOJ 3511 Cake Robbery(线段树)
ZOJ 3511 Cake Robbery(线段树)
ZOJ 3511 Cake Robbery
题目链接
题意:给定一个n边形,切m刀,问切了之后最大边数的子块边数是多少,保证切的边不会交叉
思路:由于有保证切的边不交叉这个条件,所以可以按切掉点数排序,点数最少优先切,因为点数最少肯定是被包含了,这样一刀刀切过去,切过的点就剔除掉,并记录下最大值,利用线段树维护即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 10005; int n, m; struct Query { int l, r; void read() { scanf("%d%d", &l, &r); if (l > r) swap(l, r); } } q[N]; bool cmp(Query a, Query b) { return a.r - a.l < b.r - b.l; } #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r, sum; int lazy; void gao() { lazy = 1; sum = 0; } } node[N * 4]; void pushup(int x) { node[x].sum = node[lson(x)].sum + node[rson(x)].sum; } void pushdown(int x) { if (node[x].lazy) { node[lson(x)].gao(); node[rson(x)].gao(); node[x].lazy = 0; } } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].lazy = 0; if (l == r) { node[x].sum = 1; return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x); } void add(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) { node[x].gao(); return; } int mid = (node[x].l + node[x].r) / 2; pushdown(x); if (l <= mid) add(l, r, lson(x)); if (r > mid) add(l, r, rson(x)); pushup(x); } int query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].sum; int mid = (node[x].l + node[x].r) / 2; int ans = 0; pushdown(x); if (l <= mid) ans += query(l, r, lson(x)); if (r > mid) ans += query(l, r, rson(x)); pushup(x); return ans; } int main() { while (~scanf("%d%d", &n, &m)) { build(1, n); int l, r; for (int i = 0; i < m; i++) q[i].read(); sort(q, q + m, cmp); int ans = 0; for (int i = 0; i < m; i++) { ans = max(ans, query(q[i].l, q[i].r)); add(q[i].l + 1, q[i].r - 1); } ans = max(ans, node[0].sum); printf("%d\n", ans); } return 0; }
ZOJ 3511 Cake Robbery(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。