1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1186 Solved: 640
[Submit][Status][Discuss]
Description
农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查,他发现:虽然他不能预见明天产奶的质量,但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时,这个长度为4。
Input
* Line 1: 两个整数 N,K。
* Lines 2..N+1: 每行一个整数表示当天的质量值。
Output
* Line 1: 一个整数:N天中最长的出现了至少K次的模式的长度
Sample Input
8 2
1
2
3
2
3
2
3
1
Sample Output
4
HINT
Source
Gold
列表内某范姓同学和某尹姓同学差点坑害我 我就是要先贴单调队列
先声明 这个题单调队列绝对是对的 因为他和二分完全等价
单调队列的话,我们考虑其向前k-1个数内的最小值(为什么不是k个?因为height数组的定义)
答案是最小值内的最大值
而分的话 我们考虑k-1个height数组内的最小值是否满足 满足即可
可以发现 这两个条件完全可以转化 因为最小值满足时的最大值一定就是最小值内的最大值
(md其实我这篇文章纯粹是发泄一下愤怒,坑了我两节课进去就为了验证这个本来就对的结论,最重要的是我拿一个没处理0的代码自信的说我绝对没错 mdzz 反正我改完了肯定是对的)
顺便留组数据警示后人
4 2
1
0
0
0
答案是2
为了发泄愤怒,我只贴单调队列的板子,二分的自己脑补一下应该能出来。
/*In Search Of Life*/
#include
#include
#include
#include
#include
#include
#include
#include
#include