| 题目名称 | 780. [SOJ 1137] 河床 |
|---|---|
| 输入输出 | riverbed.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-04-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：125， 通过率：18.4% | ||||
 サイタマ |
100 | 0.001 s | 0.43 MiB | C++ |
 father |
100 | 0.002 s | 0.43 MiB | C++ |
 _WA自动机 |
100 | 0.010 s | 0.40 MiB | C++ |
 Makazeu |
100 | 0.013 s | 0.40 MiB | C++ |
 QhelDIV |
100 | 0.014 s | 1.27 MiB | C++ |
 lch |
100 | 0.021 s | 0.31 MiB | C++ |
 不需要黄桃 |
100 | 0.021 s | 0.43 MiB | C++ |
 据说这是zzy |
100 | 0.026 s | 0.31 MiB | C++ |
 小字、小瓶子 |
100 | 0.027 s | 0.58 MiB | C++ |
 苏轼 |
100 | 0.027 s | 3.26 MiB | C++ |
| 本题关联比赛 | |||
| 20120419s | |||
| 关于 河床 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
应楼上要求发代码
| ||||
|
没人公开代码？
st表水过 | ||||
|
大暴搜上榜..
不需要黄桃
2017-07-11 11:15
5楼
| ||||
|
强行ST求区间最值，由于区间右端点右移时左端点要么右移要么不动，所以再扫一次即可
 liu_runda
2016-05-08 06:14
4楼
| ||||
|
强行ST求区间最值差，因为极差满足单调性，然后二分即可，时间复杂度O(nlogn),但是比优先队列慢
 Satoshi
2015-10-11 12:58
3楼
| ||||
|
谁这么无良没有数据就评测了！
 王者自由
2012-04-19 11:39
2楼
| ||||
|
Kao，交錯了。 交到題目上來了！！！！
Makazeu
2012-04-19 08:48
1楼
| ||||
kZime【问题描述】
地理学家对一段河床进行测量分析。他们从上游到下游等距离的选择了n(<=30000)个水位点深度。得到一组数据d1，d2...dn，回到实验室后数据分析员根据需要对数据进行分析，发掘隐藏在数据背后的规律。最近，乌龙博士发现某种水文现象与河床地势有关，于是他指示分析员要找出一段河流中最大高低起伏差不超过k（<=100)的最长一段。这看似一个复杂的问题，由于任务紧急，分析员来求助于你，并告诉你博士的所有数据都精确到个位。
【输入】
输入格式（输入文件名riverbed.in）
输入文件有2行。
第一行为整数n和k，分别表示测量点的个数和博士要求的最大水深差（也就是河床地势差）
第二行有n个数，为d1,d2,...dn且都是非负整数(di<=32767)
【输出】
输出格式（输出文件名riverbed.out）
输出文件只有1行，是整数m，表示最长一段起伏不超过k的河流长度，用测量点个数表示。
【输入输出样例】
样例输入（riverbed.in）
6 2
5 3 2 2 4 5
样例输出(riverbed.out)
4
样例提示
从第二个测量点到第五个测量点之间的一段，即5 (3 2 2 4) 5，起伏最大为4-2=2。