[问题] 最长的连续假期

楼主: stdlib (我是新手)   2018-11-19 04:44:04
Q: 给定一个 bool array,0代表放假日,1代表要上班
以及给一个年假天数 v,试求出请了 v 天假后,最长的连续假期天数为何
Example:
Input: {1, 0, 0, 1, 1, 0, 0, 1, 1} ; v=2
Output: 6,请了 2 天假之后 (把 1 标成 0),
阵列会变成 {1, 0, 0, 0, 0, 0, 0, 1, 1},有 6 个连续的 0。
Input: {0, 1, 1, 0, 1, 0, 1, 1, 1, 0} ; v=3
Output: 6,把前 3 个 1 标成 0,
阵列会变成 {0, 0, 0, 0, 0, 0, 1, 1, 1, 0},有 6 个连续的 0。
感谢各位大神
作者: s89162504 (阿本)   2018-11-19 17:03:00
相当于求 连续和为v的最长阵列 对吧!?简单用个two pointer就行了吧如果目前连续和比v小就head往前走如果连续和超过v就tail往前y
作者: cutekid (可爱小孩子)   2018-11-19 19:21:00
推楼上 s 大,超过 v 时,tail往前直到遇到 1 为止
作者: HanaYukii (ShioRin)   2018-12-03 14:39:00
每个起点二分搜

Links booklink

Contact Us: admin [ a t ] ucptt.com