枚举+优化（6）——双指针优化2
例3.题目链接：hihoCoder1514
ans = MAX_INT
For i = 1...M
{
For j = 1...N
{
For k = 1...L
{
s = |Ai - Bj| + |Bj - Ck| + |Ai - Ck|
IF s < ans
ans = s
}
}
}
print ans这个算法的时间复杂度是O(NML)，NML是三个数组的长度，最大值都是10万，显然会超时
优化1
第一个数组是0，1，3，8，12，15，我们从中选中了8。第二个数组是1，2，4，5，10，13，第三个数组未知，什么清空都有可能。假设现在已经确定第一个数组选出8，我们从直觉上肯定会选像5，10这样的离8近的数，不会选1，13这样离8很远的数，下面我们仔细分析一下，假如选8，那到底是选4还是选5，或者是选10 事实上可以证明，假设我们从第一个数组里选的是A[i]，那么我们第二个数组里选出的数一定<font color = red >是“小于等于A[i]的数里最大的”以及“大于等于A[i]的数里最小的”二选一</font>。例如在上面的例子中，我们已经确定了第一个数组选8，那么我们在第二个数组里只用考虑5和10，小于5的数一定不会比5更优，大于10的数一定不会比10更优。
我们看上面的图，三条黑色水平线是3个数轴，代表三个数组。数轴上的方块代表相应数组中的一个数，并且方块越靠右，代表数越大。我们假设从A数组中选出黄色方块这个数，假设C数组挑选的数是紫色方块，在绿色方块的右边，比绿色方块大，这时选蓝色方块时，3个数的差是3段蓝色的区间。选绿色方块时，3个数的差是3段绿色的区间，显然蓝色的长度和小于绿色的长度和。
再看上图，是另一种情况，假设C数组挑选的数在绿色方块左边，这时可以看到蓝色区间和绿色区间的长度相等，所以综上所述，选绿色一定不比选蓝色优。 有了这个结论我们就可以利用双指针的思路了。首先我们把3个数组都排序，然后依次枚举A数组中的一个数A[i]，表示我们从A数组挑选出的数是A[i]。这时，我们求出B数组的一个下标j，满足B[j-1] <= A[i] <= B[j]，然后再求出C数组的一个下标k，满足C[k-1] <= A[i] <= C[k]。因为我们知道包含A[i]的最优解一定在B[j-1]和B[j]中二选一，C[k-1]和C[k]中二选一，总共四种情况：（A[i],B[j-1],C[k-1]），（A[i],B[j],C[k-1]），（A[i],B[j-1],C[k]），（A[i],B[j],C[k]）
#include<iostream>
#include <algorithm>
using namespace std;
long long ans = 1000000000000000L;
void test(long long x,long long y,long long z)
{
long long d = abs(x - y) + abs(x - z) + abs(y - z);
ans = ans>d?d:ans;
}
int main()
{
int n,m,l;
cin >> n >> m >> l;
int a[100010],b[100010],c[100010];
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= m;i++)
cin >> b[i];
for(int i = 1;i <= l;i++)
cin >> c[i];
a[0] = b[0] = c[0] = -1000000000;//为了保证比a[i]小的数一定存在
a[n + 1] = b[m + 1] = c[l + 1] = 1000000000;//为了保证比a[i]大的数一定存在
sort(a,a + n + 1);
sort(b,b + m + 1);
sort(c,c + l + 1);
for(int i = 1,j = 0,k = 0;i <= n;i++)
{
while(b[j + 1] < a[i])
j++;
while(c[k + 1] < a[i])
k++;
test(a[i],b[j],c[k]);
test(a[i],b[j + 1],c[k]);
test(a[i],b[j],c[k + 1]);
test(a[i],b[j + 1],c[k + 1]);
}
cout << ans;
return 0;
}例4.题目链接：hihoCoder1607
思路
一般的暴力枚举这题肯定是过不了的，数据量太大，那我们就要想办法优化，能不能只枚举Ai，而将符合条件的Aj数量直接算出来，而不是枚举出来。其实我们仔细分析一下题目的三个条件，就能看出对于某个确定的Ai来说，他发的好友请求Aj一定是在某个年龄区间的。 比如假设Ai=8，那么年龄在[9,72]闭区间的用户都会被发送好友请求。并且随着Ai增大，这个年龄区间也是在逐渐向右移动的。向右移动是指区间的左右端点都是增大的，不会减小
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for(int i = 0;i < n;i++)
cin >> a[i];
sort(a.begin(),a.end());
int l = 0,r = -1;
long long ans = 0;
for(int i = 0;i < n ;i++)
{
while(l < n && a[l] * 8 < a[i] + 64)
l++;
while(r + 1 < n && a[r + 1] <= a[i] * 8 + 8
&&(a[i] >= 88888 || a[r + 1] <= 88888))
r++;
if(l <= r)
{
ans += (r - l + 1);
if(i >= l && i <= r)//如果这个区间包含i，就要减掉
ans--;
}
}
cout << ans;
return 0;
}腾讯云开发者
