﻿ 洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle - 鸿网互联

# 洛谷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
```

## 说明

【样例说明】

zhw讲的做法是线段树

然后根据这条线段的权值进行分类讨论就好

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=100001;
{
char c=getchar();bool flag=0;n=0;
while(c<'0'||c>'9')	c=='-'?flag=1,c=getchar():c=getchar();
while(c>='0'&&c<='9')	n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
}
struct node
{
int bg,ed,num;
}cow[MAXN];
int comp(const node &a,const node &b)
{
if(a.ed!=b.ed)	return a.ed<b.ed;
else return a.bg<b.bg;
}
int have[MAXN];// 在i这个位置，车上已经装了多少奶牛
int main()
{
int k,n,m;
for(int i=1;i<=k;i++)
sort(cow+1,cow+k+1,comp);
int ans=0;
for(int i=1;i<=k;i++)
{
if(have[cow[i].bg]>=m) continue;
int now=0x7fffff;
for(int j=cow[i].bg;j<=cow[i].ed;j++)
{
now=min(now,m-have[j]);
if(now==0) break;
}
if(now!=0)
{
if(now>=cow[i].num)
{
for(int j=cow[i].bg;j<cow[i].ed;j++)
have[j]+=cow[i].num;
ans+=cow[i].num;
}
else
{
for(int j=cow[i].bg;j<cow[i].ed;j++)
have[j]+=now;
ans+=now;
}
}
}
printf("%d",ans);
return 0;
}
```

<