题解：AT_tkppc2016_c 有給休暇（Paid Vacation）

· · 题解

题目：AT_tkppc2016_c 有給休暇（Paid Vacation）

思路

首先看到这道题目，第一眼想到暴力，双重 for 循环枚举判断，统计最大值。但是！看到数据范围 1 \leq N \leq10^5，至少是 O(n~\log_2~n) 才有可能过啊！而用前缀和优化过后还是 O(n^2)，洛谷评测机跑 10^8 都够呛，10^{10} 根本跑不完啊，绝对 TLE。

那么，我们想一想学过的算法中，哪一种算法可以处理区间呢，答案是双指针，没学过的可以百度或者去b站搜，提供一个个人认为不错的 文章，或者这个 视屏，这两个都是讲了快慢指针和双向指针的，比较全面，那么为什么双指针是可以过的呢，因为快指针和慢指针都只是走完了全程，没有多走，而且每次都必定会让慢指针移动，所以总的时间复杂度就是 O(n)。

既然已经知道了用双指针算法，那么要用那种呢（指快慢指针和双向指针），分析题意，如果我们用快慢指针，判断这个框选的区间内个数是否小于 k 的话，可以发现，是可以实现的（具体方法后面介绍），但是如果用双向指针，一下子就框柱整个区间，可以发现，很难得到最优解（是可以得到一个答案但不一定最优），那么确定了算法，就可以开始具体分析了。

首先，定义一个慢指针 l 一直往前跑，然后定义一个快指针 r，至于为什么 r 是快指针是因为我们框定的区间是 [l,r]，那么我们当然要找到从 l 开头的最大的区间和啊！记住由于双指针只能框定区间，不能确保最大值，所以要在所有的以 l 为开头的区间中取最大值。

然后，写好模版。

while (l < r)
{
    l++;
    while (条件)
        ++r;
    maxn = max(maxn, r - l);
}

接着，我们来分析一下条件。因为要保证 [l,r] 这个区间的和不能大于 k，所以第一个条件是 sum[r] - sum[l - 1] <= k（sum 为前缀和数组），然后，我们知道快指针再快也不能飞出去这个数组啊，所以第二个条件是 r <= n，只有同时满足这两个条件才能 ++r。

那么我们就写完了双指针的部分。

while (l < r)
{
    l++;
    while (sum[r] - sum[l - 1] <= k && r <= n)
        ++r;
    maxn = max(maxn, r - l);
}

然后再讲一个细节，读入的时候，记得用异或运算取反，因为要求的是原本不放假的天数而不是放假的天数。

最后再给不了解前缀和的萌新们科普一下这道题怎么用前缀和优化。定义 sum_i 表示前 i 天总共有多少个不放假的天数，那么状态转移方程就是 sum_i=sum_{i-1}+a_i，另外 a 数组可以不用开，直接用 bool 变量代替就行了，直接替换到 a_i 的位置就行了，那么求 [l,r] 这个区间内的不放假天数就是 sum_r - sum_{l-1}，具体见代码。

ACCODE

#include <iostream>
using namespace std;

int n, k, sum[100001], maxn, l, r = 1;//sum是前缀和数组，sum[i]表示1~i天有多少天是不放假的
bool tmp;//输入用

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> tmp, tmp ^= 1, sum[i] = sum[i - 1] + (int)tmp;//记得对输入数据用异或取反！
    while (l < r)//双指针模版，思路已经讲的很清楚了吧
    {
        l++;
        while (sum[r] - sum[l - 1] <= k && r <= n)
            ++r;
        maxn = max(maxn, r - l);//取最大值
    }
    cout << maxn;
}