USACO09FEB 庙会班车 Fair Shuttle

发表于

洛谷1607 BZOJ1577

  • 题意
    为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠$N(1 \le N \le 20000)$个地点（所有地点都以1到$N$之间的一个数字来表示）。现在奶牛们分成$K(1 \le K \le 50000)$个小组，第$i$组有$M_i(1 \le M_i \le N)$头奶牛，他们希望从$S_i$跑到$T_i(1 \le Si \lt Ti \le N)$。由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是$C(1 \le C \le 100)$，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
  • Solution
    • 看见“允许分开乘坐”是好事，因为这算是贪心的标志吧。
    • 两只奶牛，终点靠前的先选。这条性质分别讨论一下两条线段的关系很容易发现，不会有更优解。
    • 对于每一堆奶牛，能上多少就上多少，但是到底能上多少呢？要看看从上车到下车目前的空位最少是多少。线段树维护奶牛最大（小）值即可。
  • tip 注意询问和更新时终点是前一位，细节问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 2e4+5, maxm = 5e4+5 ;
struct node {
	int st, end, val ;
	friend bool operator < ( node a, node b ) {
		return a.end==b.end? a.st>b.st : a.end<b.end ;
	}
} s[maxm] ;
int n, m, c, tree[maxn<<2], tag[maxn<<2] ;
void push_up ( int h ) { tree[h] = max(tree[h<<1], tree[h<<1|1]) ; }
void push_down ( int h ) {
	if (tag[h]) {
		tag[h<<1] += tag[h] ;
		tag[h<<1|1] += tag[h] ;
		tree[h<<1] += tag[h] ;
		tree[h<<1|1] += tag[h] ;
		tag[h] = 0 ;
	}
}
int query ( int h, int l, int r, int x, int y ) {
	if ( x <= l && r <= y ) return tree[h] ;
	int mid = (l+r)>>1 ;
	push_down(h) ;	
	if ( y <= mid ) return query ( h<<1, l, mid, x, y ) ;
	else if ( x > mid ) return query ( h<<1|1, mid+1, r, x, y ) ;
	else return max( query ( h<<1, l, mid, x, mid ), query ( h<<1|1, mid+1, r, mid+1, y ) ) ;
}
void update ( int h, int l, int r, int x, int y, int v ) {
	if ( x <= l && r <= y ) {
		tree[h] += v ;
		tag[h] += v ;	
		return ;
	}
	int mid = (l+r)>>1 ;
	push_down(h) ;	
	if ( y <= mid ) update ( h<<1, l, mid, x, y, v ) ;
	else if ( x > mid ) update ( h<<1|1, mid+1, r, x, y, v ) ;
	else {
		update ( h<<1, l, mid, x, mid, v ) ;
		update ( h<<1|1, mid+1, r, mid+1, y, v ) ;
	}
	push_up(h) ;
}
int main() {
#ifndef ONLINE_JUDGE
	freopen ( "LG1607.in", "r", stdin ) ;
	freopen ( "LG1607.out", "w", stdout ) ;
#endif
	int i, k ;
	Read(m) ; Read(n) ; Read(c) ;
	for ( i = 1 ; i <= m ; i ++ ) {
		Read(s[i].st) ;
		Read(s[i].end) ;
		Read(s[i].val) ;
	}
	sort ( s+1, s+m+1 ) ;
	int ans = 0 ;
	for ( i = 1 ; i <= m ; i ++ ) {
		k = query ( 1, 1, n, s[i].st, s[i].end-1 ) ;
		if ( k >= c ) continue ;
		if ( c - k >= s[i].val ) ans += s[i].val, update ( 1, 1, n, s[i].st, s[i].end-1, s[i].val ) ;
		else ans += c-k, update ( 1, 1, n, s[i].st, s[i].end-1, c - k ) ; 
	}
	cout << ans << endl ;
	return 0 ;
}