BZOJ 1577: [Usaco2009 Feb]庙会捷运Fair Shuttle

题目地址

描述

公交车一共经过$N(1 \leq N \leq 20000)$个站点,从站点$1$一直驶到站点$N$。$K(1\leq K \leq 50000)$群奶牛希望搭乘这辆公交车,第$i$群牛一共$M_{i}(1\leq M_{i} \leq N)$只,他们希望从$S_{i}$到$E_{i}$去。
公交车只能坐$C(1\leq C \leq 100)$只奶牛,而且不走重复路线,请计算这辆车最多能满足多少奶牛听要求。
注意:对于每一群奶牛,可以部分满足,也可以全部满足,也可以全部不满足。

分析

蒟蒻日常一水QAQ
看到这个题目很容易想到贪心,实际上这道题目本质就是一道贪心的经典题目“活动安排问题”。

首先我们按照每一群奶牛的终点排序,若终点相同则按照起点排序。
然后用一个数组$b[]$来维护$1 \sim n$每个结点上的最多奶牛数量。
然后$1 \sim k$只奶牛从前到后扫一遍,对于每一只奶牛$i$若$b[i] < c$则可以继续考虑,否则考虑下一只奶牛。
对于每一只被考虑的奶牛,记一只奶牛从$s$到$e$中最少能够再加入的奶牛只数$temp$(相当于维护了每一个结点奶牛数量尽可能多),然后对于奶牛所处的$s$到$e$的结点扫一遍更新$temp$。
然后考虑$temp$大于等于当前奶牛群只数的情况以及小于的情况,更新$b[]$以及$ans$。

在数据范围较小的时候,这样做是可以水过去的,但是在数据范围较大的时候还是需要用线段树来维护区间的最大值,所以我明天再来补一下用线段树维护的版本吧QAQ

代码

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
//  BZOJ 1577 [Usaco2009 Feb]庙会捷运Fair Shuttle
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 20000 + 3;
const int MAX_K = 50000 + 3;
const int INF = 0x3f3f3f3f;
int k, n, c;// cows, points, contain
struct Node {
int s, e, m;
bool operator < (const Node &rhs) const {
if (e == rhs.e) return s < rhs.s;
return e < rhs.e;
}
}a[MAX_K];
int b[MAX_N], ans, temp;

int main()
{
k = readIn(), n = readIn(), c = readIn();
for (int i = 0; i < k; ++i) a[i].s = readIn(), a[i].e = readIn(), a[i].m = readIn();
sort(a, a + k);

ans = 0, temp = 0;
memset(b, 0, sizeof b);
for (int i = 0; i < k; ++i) {
temp = INF;
if (b[a[i].s] < c) {
for (int j = a[i].s; j < a[i].e; ++j) {
temp = min(temp, c - b[j]);
if (temp == 0) break;
}
if (temp != 0) {
if (temp >= a[i].m) {
for (int j = a[i].s; j < a[i].e; ++j) b[j] += a[i].m;
ans += a[i].m;
}
else {
for (int j = a[i].s; j < a[i].e; ++j) b[j] += temp;
ans += temp;
}
}
}
}
printf("%d\n", ans);
return 0;
}
Partager