算法入门之枚举优化（三） 双指针 未完待续。。。。

双指针的思路：有时我们要对一个数组进行i和j的俩个下标的双重循环枚举：

此时时间复杂度为o（n^2）

此时我们可以利用双指针进行优化：

双指针的思路是什么呢？就是在某些情况下，根据题目要求，j下标并不需要从i+1开始重新向后枚举一遍，而是跟随着i向后移动，j也向后移动。 

例题：

 我们来具体看一道题。
给定N个整数A1， A2， … ，AN，以及一个正整数K。问在所有的大于等于K的两个数的差(Ai-Aj)中，最小的差是多少。(N <= 100000)

思路一：这个题目当然可以用2重循环来做，复杂度是O(N^2)的。代码大概是这个样子：

for(int i=0; i<n; i++){
    for（int j=0; j<n; j++）{
      if (a[i]-a[j]>=k && a[i]-a[j]<ans)
        ans=a[i]-a[j]
}
}

 那我们怎么用双指针优化呢？首先就是对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

#include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n, k, min;
 8     int a[100000];
 9     
10     cin >> n >> k;
11     for(int i = 0; i < n; i ++)
12         cin >> a[i]; 
13     sort(a, a + n);        
15     if(a[n-1] - a[0] < k )
16     {
17         cout << "no solution" << endl;
18         return 0;    
19     } 
21     min = a[n-1] - a[0];
22     int j = 0;
23     for(int i = 0; i < n; i ++)
24     {
25         while( j <= n - 1 && a[j] - a[i] < k )
26             j ++;
27         if(a[j] - a[i] >= k && a[j] - a[i] < min)
28             min = a[j] - a[i];
29     }
30     cout << min << endl;
32     return 0;
33 } 

此时利用双指针找出相对于前面那个数的最优解，循环下一个数时最优解也准备不动或后移

例题2

Problem Description

soda has an integer array a1,a2,…,an. Let S(i,j) be the sum of ai,ai+1,…,aj. Now soda wants to know the value below:

∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)

Note: In this problem, you can consider log20 as 0.

 

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤105), the number of integers in the array.
The next line contains n integers a1,a2,…,an (0≤ai≤105).

 

Output

For each test case, output the value.

 

Sample Input

1 2 1 1

 

Sample Output

12

 

解答稍后。。。。。。。

例题三

这个题大意是这样：我们把连续的K个整数称作一个顺子。比如K=5的时候，1-2-3-4-5就是一个顺子，13-14-15-16-17也是一个顺子；K=7的时候，顺子就要更长，比如3-4-5-6-7-8-9是一个顺子。现在我们已经有了N个整数A1, A2, … AN。然后我们还有M张百搭卡片，每一张都可以当作一个任意的整数。问你通过已经有的N个整数和M张百搭牌，能组成的最大顺子是哪个。这里最大指的是顺子中的最大整数最大。比如5-6-7-8-9就比1-2-3-4-5大，10-11-12-13-14比5-6-7-8-9大。

当然题意中的百搭卡片的数量M是小于k的

思路一：暴力枚举

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

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

这个算法的时间复杂度是o（pk）的显然我们需要更近一步的优化。

思路二：

 第一个能优化的地方是对于X的枚举，也就是顺子开头的数值。经过分析我们能知道，如果X-(X+1)-(X+2)-…-(X+K-1)是能凑出来的最大顺子。那么X一定是已经存在的数，也就是A数组中的某个数。
因为如果最大的顺子是X-(X+1)-(X+2)-…-(X+K-1)，但是X是使用百搭卡变出来的，那么我们可以让这张百搭卡变成X+K，这样就能凑出来一个更大的顺子(X+1)-(X+2)-…-(X+K)。

未完待续。。。。。。。。。