枚举+优化（5）——双指针优化1

有时候我们要对一个数组进行i和j两个下标的双重循环枚举

for(int i = 0;i < n;i++)
{
    for(int j = i + 1;j < n;j++)
    {
        ...
    }
}

从上面的代码我们能看出时间复杂度是$O(N^2)$

双指针优化

在某些情况下，根据题目要求，j下标并不需要从i+1重新往后枚举一遍，而是跟随着i向后移动，j也向后移动

当红色i下标向右移动时，绿色下标不会向左移动。它有可能不动，也有可能向右，但是不会向左。由于j坐标不会向左移动，所以整个枚举的复杂度是$O(N)$

例1

给定N个整数$A_1,A_2,...,A_N$，以及一个正整数k。问在所有的大于等于k的两个数的差$A_i-A_j$中，最小的差是多少？（N<=100000）

思路

首先对A数组排序，比如假设排好序的A数组是：A=[1,3,7,8,10,15]，k=3，这时我们枚举两个数中较小的是A[i]，较大的是A[j]；对A[i]来说，我们要找到最优的A[j]，也就是最小的A[j]满足A[j] - A[i] >= k

从上面的图我们可以看出：当A[i]=1时，最优的A[j]=7；当A[i]=3时，最优的A[j]=8；当A[i]=7时，最优的A[j]=10，这个“最优的A[j]”要么不动要么向右，不会向左。换句话说，我现在已知A[i]=1的时候，A[j]=7是最优的解；那么当A[i]变成3的时候，A[j]就可以从7的位置向后找，不用向前找

#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n,k,ans,a[10000];
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    sort(a,a + n);
    if(a[n - 1] - a[0] < k){
        cout << "no solution" << endl;
        return 0;
    }
    ans = a[n - 1] - a[0];
    for(int i = 0,j = 0;i < n;i++)//枚举A[i]
    {
        while(j < n && a[j] - a[i] < k)
            j++;
        if(a[j] - a[i] >= k && a[j] - a[i] < ans)
            ans = a[j] - a[i];
    }
    cout << ans;
    return 0;
} 

例2 题目链接：hihoCoder1745

思路1：暴力枚举

假设$A_1~A_N$的最大值是P，那么可能凑出的最大顺子就是（P,P+1,P+2,...,P+k-1），所以我们先检查一下这个P开头的顺子能不能凑出来，如果不能，我们再尝试P-1开头的顺子能不能凑出来......直到试出某个顺子能凑出来。伪代码如下：

for X = p,p-1,p-2,...,0
    if 能凑出 (x,x + 1,x + 2,...,x + k - 1)
        return x + k - 1

以题目样例为例，由于k=5，现有最大整数是13。我们先试（13，14，15，16，17），再试（12，13，14，15，16）,......试到（7，8，9，10，11），发现这个顺子能凑出来，因为只有一个9没有，可以用一张百搭卡片凑。

检查X开头的顺子是否能凑出来的算法是，枚举X~(X+K-1)这K个数中，有几个在现有的整数中，有几个不在，需要用百搭卡。如果需要的百搭卡数量超过M，那这个顺子就凑不出来，伪代码如下：

Hashtable <- [A1,A2,...,AN]
need_card = 0
for i = X,X + 1,...,X + k - 1
    if not Hashtable.find(i)
        need_card++;
return need_card <= M

这样整个算法的时间复杂度是O(PK)，P是这个数组的最大值，所以有可能有$10^8$这么大，K最大$10^5$，显然会超时

优化1

第一个能优化的地方是对于X的枚举，也就是顺子开头的数值。经过分析我们能知道，如果(X,X+1,X+2,...,X+K-1)是能凑出来的最大顺子。那么X一定是存在数，因为如果X是百搭卡变出来的，那么我们为什么百搭卡变成X+K，这样就能凑出来一个更大的顺子(X+1,X+2,...,X+K)

优化2

第二个可以优化的地方就是判断能不能凑出X开头的顺子。我们利用双指针可以把这一步均摊时间复杂度降到O(1)。首先我们对A数组排序，然后对于每一个A[i]，我们还是找一个最优的A[j]。这里“最优”指最大的A[j]满足A[i]~A[j]之间需要的百搭卡整数不超过M张

上图是样例每个A[i] (红色箭头)对应的最优A[j(绿色箭头)]，可以看出当A[i]从大到小枚举的过程中，A[j]也是从大到小改变，不会变大，所以这个双指针枚举的复杂度是$O(N)$

对于每个A[i]，当我们求出最优的A[j]之后，就可以计算以A[i]开头的顺子能不能凑出了。而A[i]~A[j]一共需要的百搭卡是(A[j]-A[i])-(j-i)张，那么剩余的百搭卡一定是用在A[j]+1，A[j]+2...，我们只需要判断剩余的百搭卡是不是足够用到A[i]+k-1即可

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,m,k;
    vector<int>a;
    cin >> n >> m >> k;
    for(int i = 0;i < n;i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    int ans = -1;
    for(int i = n - 1,j = n - 1;i >= 0;i--)
    {
        int need_card = a[j] - a[i] - (j - i);
        while(need_card > m)
        {
            j--;
            need_card = a[j] - a[i] - (j - i);
        }
        if(a[j] + (m - need_card) - a[i] + 1 >= k)
        {
            ans = a[j] + (m - need_card);
            break;
        }
    }
    cout << ans;
    return 0;
}