首页 > 代码库 > [luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）
[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）
传送门
把线段都读进来然后排序，先按右端点为第一关键字从小到大排序，后按左端点为第二关键字从小到大排序。
注意不能先按左端点后按右端点排序，否则会出现大包小的情况，如下：
——————
———
—
然后直接线段树搞就行，先求区间最小值，如果大于零就更新统一减1。
——代码
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define root 1, 1, n 5 #define ls now << 1, l, mid 6 #define rs now << 1 | 1, mid + 1, r 7 8 const int INF = ~(1 << 31), MAXN = 100001; 9 int n, m, ans;10 int minn[MAXN << 2], add[MAXN << 2];11 12 struct node13 {14 int a, b;15 }p[MAXN];16 17 inline void swap(int &x, int &y)18 {19 x ^= y ^= x ^= y;20 }21 22 inline void push_up(int now)23 {24 minn[now] = std::min(minn[now << 1], minn[now << 1 | 1]);25 }26 27 inline void push_down(int now, int len)28 {29 if(!add[now]) return;30 add[now << 1] += add[now];31 add[now << 1 | 1] += add[now];32 minn[now << 1] += add[now];33 minn[now << 1 | 1] += add[now];34 add[now] = 0;35 }36 37 inline void build(int now, int l, int r)38 {39 if(l == r)40 {41 scanf("%d", &minn[now]);42 return;43 }44 int mid = (l + r) >> 1;45 build(ls);46 build(rs);47 push_up(now);48 }49 50 inline bool cmp(node x, node y)51 {52 return x.b == y.b ? x.a < y.a : x.b < y.b;53 }54 55 inline int query(int x, int y, int now, int l, int r)56 {57 if(x <= l && r <= y) return minn[now];58 if(l > y || r < x) return INF;59 push_down(now, r - l + 1);60 int mid = (l + r) >> 1;61 return std::min(query(x, y, ls), query(x, y, rs));62 }63 64 inline void update(int x, int y, int now, int l, int r)65 {66 if(x <= l && r <= y)67 {68 minn[now]--;69 add[now]--;70 return;71 }72 if(l > y || r < x) return;73 push_down(now, r - l + 1);74 int mid = (l + r) >> 1;75 update(x, y, ls);76 update(x, y, rs);77 push_up(now);78 }79 80 int main()81 {82 int i, j;83 scanf("%d %d", &n, &m);84 build(root);85 for(i = 1; i <= m; i++)86 {87 scanf("%d %d", &p[i].a, &p[i].b);88 if(p[i].a > p[i].b) swap(p[i].a, p[i].b);89 }90 std::sort(p + 1, p + m + 1, cmp);91 for(i = 1; i <= m; i++)92 if(query(p[i].a, p[i].b, root) > 0)93 ans++, update(p[i].a, p[i].b, root);94 printf("%d", ans);95 return 0;96 }
[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。