Talk is Cheap, Show Me the Code!

0%

集市班车

Posted on In

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠N个地点（所有地点都以1到N之间的一个数字来表示）。
现在奶牛们分成K个小组，第i组有M_i头奶牛，他们希望从S_i跑到T_i。由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C ，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。

输入描述:

第一行包括三个整数K N C，彼此用空格隔开。
第二行到K+1行：在第i+1行，将会告诉你第i组奶牛的信息：S_i,E_i和M_i，彼此用空格隔开。

输出描述:

可以坐班车的奶牛的最大头数。

示例1
输入

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

输出

10

说明

班车可以把两头奶牛从1送到5，三头奶牛从5送到8，两头奶牛从8送到14，一头奶牛从9送到12，一头奶牛从13送到14，一头奶牛从14送到15。
2<=N<=10000, 1<=K<=50000, 1<=C<=100

jishibanche.cppview raw
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
72
73
74
75
76
/*
 按照下车地点从小到大排序之后，早下车的一定要优先选取
 每次决策，先算出当前区间上车子最多有多少乘客
 那么剩下的位置安排给当前这批
 用线段树维护每个点车上的乘客数
 需要支持区间最值 和 区间加值
 */
#include<bits/stdc++.h>
#define M 10005
#define N 50005
using namespace std;
struct node {
    int s,e,m;
} A[N];
bool cmp(node w1,node w2) {
    return w1.e<w2.e;
}
struct Node {
    int L,R,mx,add;
} tree[M<<2];
void up(int p) {
    tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
}
void down(int p) {
    if(!tree[p].add)return;
    tree[p<<1].add+=tree[p].add;
    tree[p<<1].mx+=tree[p].add;
    tree[p<<1|1].add+=tree[p].add;
    tree[p<<1|1].mx+=tree[p].add;
    tree[p].add=0;
}
void build(int L,int R,int p) {
    tree[p].L=L,tree[p].R=R,tree[p].mx=0,tree[p].add=0;
    if(L==R)return;
    int mid=(L+R)>>1;
    build(L,mid,p<<1);
    build(mid+1,R,p<<1|1);
}
void update(int L,int R,int p,int a) {
    if(tree[p].L==L&&tree[p].R==R) {
        tree[p].mx+=a;
        tree[p].add+=a;
        return;
    }
    down(p);
    int mid=(tree[p].L+tree[p].R)>>1;
    if(R<=mid)update(L,R,p<<1,a);
    else if(L>mid)update(L,R,p<<1|1,a);
    else update(L,mid,p<<1,a),update(mid+1,R,p<<1|1,a);
    up(p);
}
int query(int L,int R,int p) {
    if(tree[p].L==L&&tree[p].R==R)return tree[p].mx;
    down(p);
    int mid=(tree[p].L+tree[p].R)>>1;
    if(R<=mid)return query(L,R,p<<1);
    if(L>mid)return query(L,R,p<<1|1);
    return max(query(L,mid,p<<1),query(mid+1,R,p<<1|1));
}
int main() {
    int k,n,c,ans=0;
    scanf("%d%d%d",&k,&n,&c);
    for(int i=1;i<=k;i++)
        scanf("%d%d%d",&A[i].s,&A[i].e,&A[i].m);
    sort(A+1,A+1+k,cmp);
    build(1,n,1);
    for(int i=1;i<=k;i++) {
        int mx=query(A[i].s,A[i].e-1,1);
        mx=max(c-mx,0);
        mx=min(mx,A[i].m);
        update(A[i].s,A[i].e-1,1,mx);
        ans+=mx;
    }
    printf("%d\n",ans);
    return 0;
}