我不会做啊……贪心题啊……题啊……啊……
我真TM菜爆了啊……
这题就像一样，把终点排序，终点相同的按起点排序。然后维护一个查询最大值的线段树。对于一个区间[l,r]，如果这个区间已经有的最大值为s，那么这个区间最多还能装下c-s头奶牛。
当然奶牛数量没那么多的话我也是没有办法
最后说一句，奶牛到终点就下车了，可以给别的奶牛腾空间，不计入个数。所以奶牛在车上的区间为[l,r-1]。
#include#include #include #define N 100001#define min(x, y) ((x) < (y) ? (x) : (y))#define max(x, y) ((x) > (y) ? (x) : (y))#define root 1, 1, n#define ls now << 1, l, mid#define rs now << 1 | 1, mid + 1, rint k, n, c, ans;int sum[N << 2], add[N << 2];struct node{ int s, t, m;}p[N];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; return x * f;}inline bool cmp(node x, node y){ return x.t < y.t;}inline void pushdown(int now){ if(add[now]) { sum[now << 1] += add[now]; sum[now << 1 | 1] += add[now]; add[now << 1] += add[now]; add[now << 1 | 1] += add[now]; add[now] = 0; }}inline int query(int now, int l, int r, int x, int y){ if(x <= l && r <= y) return sum[now]; pushdown(now); int mid = (l + r) >> 1, ret = 0; if(x <= mid) ret = max(ret, query(ls, x, y)); if(mid < y) ret = max(ret, query(rs, x, y)); return ret;}inline void update(int now, int l, int r, int x, int y, int d){ if(x <= l && r <= y) { sum[now] += d; add[now] += d; return; } pushdown(now); int mid = (l + r) >> 1; if(x <= mid) update(ls, x, y, d); if(mid < y) update(rs, x, y, d); sum[now] = max(sum[now << 1], sum[now << 1 | 1]);}int main(){ int i, x; k = read(); n = read(); c = read(); for(i = 1; i <= k; i++) { p[i].s = read(); p[i].t = read(); p[i].m = read(); } std::sort(p + 1, p + k + 1, cmp); for(i = 1; i <= k; i++) { x = query(root, p[i].s, p[i].t - 1); if(x < c) { update(root, p[i].s, p[i].t - 1, min(p[i].m, c - x)); ans += min(p[i].m, c - x); } } printf("%d\n", ans); return 0;}