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 ;
}