| 题目名称 | 1568. [USACO Oct05]奶牛航班 |
|---|---|
| 输入输出 | cowflight.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 16 |
| 题目来源 |
 cstdio
于2014-03-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：26， 通过率：38.46% | ||||
 stdafx.h |
100 | 0.093 s | 0.58 MiB | C++ |
 wire |
100 | 0.140 s | 0.54 MiB | C++ |
 KZNS |
100 | 0.195 s | 0.54 MiB | C++ |
 gls1196 |
100 | 0.199 s | 0.55 MiB | C++ |
 cstdio |
100 | 0.203 s | 0.55 MiB | C++ |
 HouJikan |
100 | 0.209 s | 0.47 MiB | C++ |
 digital-T |
100 | 0.210 s | 0.40 MiB | C++ |
 Wang Yen Jen |
100 | 0.451 s | 0.48 MiB | C++ |
 mikumikumi |
100 | 0.656 s | 1.46 MiB | C++ |
 ONCE AGAIN |
100 | 0.665 s | 114.75 MiB | C++ |
| 关于 奶牛航班 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
强行用平衡树维护了最大值最小值和插入。
其实就是set。。。 | ||||
|
居然1A了。。。
| ||||
|
TCtower神犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇
膜拜中  Ezio
2014-07-28 11:42
3楼
| ||||
|
回复 @Chenyao :
犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇 | ||||
|
飞机如果飞到一个农场就停一下也没有关系,算法过程就是模拟飞机到每个机场都停一下,该下飞机的奶牛下飞.如果有空位,就让奶牛全部上去,如果上不去,这个时候看飞机上有没有目的地比该牧场的奶牛远的,如果有,凭什么满足目的地远的奶牛,(越近越有可能满足尽量多的奶牛),就给这头奶牛"踢回家",让目的地近的上来.可以用大根堆维护.
 Chenyao2333
2014-03-29 16:17
1楼
| ||||
【题目描述】
为了表示不能输给人类，农场的奶牛决定成立一家航空公司。她们计划每天早晨，从密歇根湖湖岸的最北端飞向最南端，晚上从最南端飞向最北端。在旅途中，航空公司可以安排飞机停在某些机场。她们需要你帮助来决定每天携带哪些乘客。
沿着湖岸，有N（1<=N<=10000）个由北至南编号为1到N的农场。每个农场都有一个机场。这天，有K（1<=K<=50000）群牛想要乘坐飞机旅行。每一群牛想要从一个农场飞往另一个农场。航班可以在某些农场停下带上全体或部分的牛。奶牛们登机后会一直停留直至达到目的地。
提供给你飞机的容量C（1<=C<=100），同时提供给你想要旅行的奶牛的信息，请你计算出这一天的航班最多能够满足几只奶牛的愿望。
【输入格式】
第1行：3个用空格隔开的整数K，N,C.
第2到K+1行：每一行有3个用空格隔开的整数S,E,M。表示有M只奶牛想从农场S乘飞机到农场E。
【输出格式】
输出一行一个正整数，既可以完成旅行的奶牛数量的最大值。
【样例输入】
4 8 3
1 3 2
2 8 3
4 7 1
8 3 2
【样例输出】
6
【提示】
样例说明：
3群想要旅行的奶牛，8个农场，飞机上有3个座位。早晨，飞机把2只牛从1带到3，1只牛从2带到8，1只牛从4带到7.晚上，航班把2只牛从8带到3.
【来源】
Hal Burch,2004
USACO Oct05