# 洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle 题解【贪心】

不是很容易写出正解的贪心问题。

## 题目描述

Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.

FJ couldn’t afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the M_i (1 <= M_i <= N) cows in group i wanting to ride from one stop S_i (1 <= S_i < E_i) to another stop E_i (S_i < E_i <= N) farther along the route.

The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.

Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

## 输入输出样例

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个座位的话直接按顺序插空。但是现在有$c$个座位了，会出现一些反例，也就是不能像排队接水那样先接在最早留空的后面。

对于每组奶牛，我们要选择上一次下车位置最接近下一次起点的座位接上去，因为这样满足了贪心，而且如果有上一次下车位置离下一次起点稍微远一点的座位，它可以创造更大的价值。下面是一个例子：

按照顺序，奶牛1会排在前面。如果奶牛1抢了座位1，那么奶牛2就坐不进去了。而奶牛1的时间实际上是可以坐进座位2的，这样给空位更大的座位1留下了创造更大价值的机会。由此可以知道，奶牛要去接在结束时间最早且在自己开始之前结束的那个座位上。因为$c$比较小，所以可以每次都排序，如果$c$太大的话需要借助线段树来辅助其他算法降低复杂度。

同时，我们是一组一组排序的，而当前总比后面的优，所以如果上图奶牛1不止1头，就可以去抢占座位1啦。统计时记得把奶牛1的数量减少，保证当前奶牛数量不为0；不然就要操作下一组奶牛了。

## Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
struct act
{
int s,t,num;
friend bool operator <(act a,act b)
{
if(a.t!=b.t)
return a.t<b.t;
return a.s<b.s;
}
}a[50010];
int End[111];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int k,n,c;
scanf("%d%d%d",&k,&n,&c);
for(int i=1;i<=k;++i)
scanf("%d%d%d",&a[i].s,&a[i].t,&a[i].num);
std::sort(a+1,a+1+k);
int sum=0;
for(int i=1;i<=k;++i)
{
std::sort(End+1,End+1+c,cmp);
for(int j=1;a[i].num&&j<=c;++j)
if(End[j]<=a[i].s)
{
++sum;
End[j]=a[i].t;
a[i].num--;
}
}
printf("%d\n",sum);
return 0;
}


Subscribe

/* */