枚举法与尺取法

First Post:

Last Update:

在之前的课程中，我们深入讨论了打表法与模拟法的暴力解法。提到暴力，我们通常会首先想到枚举。然而，枚举实际上是一门技术，要确保能够穷尽所有可能的情况并不容易。因此，在本节课中，我们将详细介绍枚举法的技巧，以确保能够完整地列举出所有情况，不漏一种。

知识点

  • 枚举法
    • 简单型枚举
    • 组合型枚举
    • 排列型枚举
    • 指数型枚举
  • 尺取算法

枚举法

枚举算法的思想：

枚举算法的核心思想是将问题的所有可能成为答案的解一一列举，然后根据问题给定的条件判断这些解是否合适。对于符合条件的解，保留；反之则舍弃。

枚举算法解题的基本思路：

  1. 确定枚举解的范围和判断条件： 在开始解题之前，需要明确枚举的解范围，并定义问题的判断条件。
  2. 选取合适的枚举方法： 选择适当的枚举方式进行逐一枚举，确保覆盖所有可能的解。避免遗漏任何真正的解，同时注意防止重复。
  3. 使用判断条件检验解： 在枚举过程中，应用事先确定的判断条件验证每个解的合法性，保留符合要求的解。

枚举算法的一般步骤：

  1. 确定范围和枚举方式： 根据题目确定枚举的范围，并选择合适的枚举方式。确保不遗漏任何真正的解，同时避免重复。
  2. 优化解空间： 查看是否存在优化的可能性，以缩小可能成为解的答案范围，提高解决问题的效率。
  3. 定义准确验证条件： 根据问题找到准确、易编码的验证条件，用于检验每个可能的解。
  4. 枚举和判断： 逐一枚举解并验证是否符合事先确定的条件，保留符合条件的解。
  5. 输出结果： 按照要求输出枚举过程中留下的符合条件的解。

枚举法包含多种技巧和方法，本节课将深入探讨其中几种方法。

简单型枚举

简单型枚举是通过简单的 for 循环嵌套解决的问题类型。在之前的课程中，我们所讨论的题目通常属于简单型枚举的范畴。因此，简单型枚举是一种相对简单且大家接触最多的枚举方式。

这种枚举方式没有特定的固定枚举模式，而且相对简单。只需按照题目的要求设计代码即可完成解题。

让我们通过一个示例题目来复习一下。

42 点问题

题目描述:

众所周知在扑克牌中，有一个老掉牙的游戏叫做 2424 点，选取 44 张牌进行加减乘除，看是否能得出 2424 这个答案。

现在小蓝同学发明了一个新游戏，他从扑克牌中依次抽出 66 张牌，注意不是一次抽出，进行计算，看是否能够组成 4242 点，满足输出 ���YES，反之输出 ��N**O。

最先抽出来的牌作为第一个操作数，抽出牌做第二个操作数，运算结果在当作第一个操作数，继续进行操作。

除不尽的情况保留整数。

请设计一个程序对该问题进行解答。

样例:

1
2
3
4
5
6
7
输入：

K A Q 6 2 3

输出：

YES

对于上面的样例我们进行了如下计算；

1
2
3
4
5
1. K*A=K 即 13*1=13
2. 13/12=1 保留整数
3. 1+6=7
4. 7*2=14
5. 14*3=42

运行限制:

1
2
最大运行时间：1s
最大运行内存: 128M

题目解析：

这个题目我们可以依次枚举数字，然后在枚举数字间的符号即可。由于到结果之间进行了三步计算，所以我们这里需要进行一个递归操作，利用了上节课讲解的知识。

两重循环即可解决问题，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
op1 赋值为 第一个数

op(op[1] op[2])
{

    for op in [+ - * /]
       ans = 第一个操作数op1 操作 第二个操作数op2

        如果是第六个操作数，就检验是否符合要要求 ==42？ 如果是就返回True

        如果op(ans , op[3]) 返回 True，就返回True 因为找到了答案，否则就继续进行

    没有找到答案返回False
}

但是这样写，思路感觉很清晰，写起来却非常的复杂，我们使用我们讲过的 Vector 来优化这个枚举方式。

我们创建 5 个 Vector ，分别用来存放 1−51−5 次的运算结果，非常简单。我们答案就采用这种方式。

答案解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
using namespace std;
int a[10];
vector <int> ans[10];
int main()
{
    for(int i=0; i<6; i++)
    {
        char c;
        cin>>c;
        if(c=='A')
            a[i]=1;
        else if(c=='J')
            a[i]=11;
        else if(c=='Q')
            a[i]=12;
        else if(c=='K')
            a[i]=13;
        else
            a[i]=(c-'0');
        //cout<<a[i]<<endl;
    }
    ans[0].push_back(a[0]);
    for(int i=1; i<=5; i++)
    {
        for(int j=0; j<ans[i-1].size(); j++)
        {
            ans[i].push_back(ans[i-1][j]+a[i]);
            ans[i].push_back(ans[i-1][j]-a[i]);
            ans[i].push_back(ans[i-1][j]*a[i]);
            ans[i].push_back(ans[i-1][j]/a[i]);
        }
    }
    //cout<<ans[5].size()<<endl;
    int flag=0;
    for(int i=0; i<ans[5].size(); i++)
    {
        if(ans[5][i]==42)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

Python 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ans = [[] for i in range(10)]
a = ['0']*10
if __name__ == '__main__':
c = input().split()
for i in range(6):
    if c[i] == 'A':
        a[i] = 1
    elif c[i] == 'J':
        a[i] = 11
    elif c[i] == 'Q':
        a[i] = 12
    elif c[i] == 'K':
        a[i] = 13
    else:
        a[i] = ord(c[i]) - ord('0')

ans[0].append(a[0])
for i in range(1, 6):
    for j in range(len(ans[i - 1])):
        ans[i].append(ans[i - 1][j] + a[i])
        ans[i].append(ans[i - 1][j] - a[i])
        ans[i].append(ans[i - 1][j] * a[i])
        ans[i].append(int(ans[i - 1][j] / a[i]))
flag = 0
for j in range(len(ans[5])):
    if ans[5][j] == 42:
        flag = 1
        break
if flag == 1:
    print("YES")
else:
    print("NO")

Java 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Scanner;
import java.util.Vector;

public class Main {

  static int[] a = new int[10];
  static Vector<Vector<Integer>> ans = new Vector<Vector<Integer>>();
  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      for (int i = 0; i < 6; i++) {

          String c;
          c = in.next();

//            System.out.println(c);

          if (c.charAt(0) == 'A')
              a[i] = 1;
          else if (c.charAt(0) == 'J')
              a[i] = 11;
          else if (c.charAt(0) == 'Q')
              a[i] = 12;
          else if (c.charAt(0) == 'K')
              a[i] = 13;
          else
              a[i] = (c.charAt(0) - '0');
//            System.out.println(a[i]);
      }
      ans.addElement(new Vector<Integer>());
      ans.get(0).addElement(a[0]);
      for(int i=1; i<=5; i++)
      {
          ans.addElement(new Vector<Integer>());
          for(int j = 0; j< ans.get(i - 1).size(); j++)
          {
              ans.get(i).addElement(ans.get(i - 1).get(j) +a[i]);
              ans.get(i).addElement(ans.get(i - 1).get(j)-a[i]);
              ans.get(i).addElement(ans.get(i - 1).get(j)*a[i]);
              ans.get(i).addElement(ans.get(i - 1).get(j)/a[i]);
          }
      }
      //cout<<ans[5].size()<<endl;
      int flag=0;
      for(int i = 0; i< ans.get(5).size(); i++)
      {
          if(ans.get(5).get(i)==42)
          {
              flag=1;
              break;
          }
      }
      if(flag==1)
          System.out.println("YES");
      else
          System.out.println(" NO");
  }
}

组合型枚举

排列组合是大家都接触过的概念，而组合型枚举则是在 �n 个元素中随机选出 �m 个元素的问题。对于每一种可能的选择方案，我们需要确定选择了哪 �m 个元素，这就 是组合型枚举。

具体而言，组合型枚举解决的是 ���Cnm 问题，即从 �n 个元素中选择 �m 个元素的组合数量。

组合型枚举有一套固定的流程和算法模板，需要大家进行记忆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
chosen = []
n = 0
m = 0

def calc(x):
  if len(chosen) > m:
      return
  if len(chosen) + n - x + 1 < m:
      return
  if x == n + 1:
      for i in chosen:
          print(i,end=' ')
      print('')
      return

  chosen.append(x)
  calc(x + 1)
  chosen.pop()
  calc(x + 1)

if __name__ == '__main__':

  tem = input().split()
  n = int(tem[0])
  m = int(tem[1])
  calc(1)
import java.util.Scanner;
import java.util.Vector;
public class Main {

    static  int n;
    static int m;//选m个数
    static Vector<Integer> chosen = new Vector<Integer>();
    static  void calc(int x) {
        if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
            return;
        if (x == n + 1) { //选够了m个数输出
            String ansTem = "";
            for (int i = 0; i < chosen.size(); i++)
                System.out.print(chosen.get(i)+" ");
            System.out.println("");
            return;
        }
        chosen.addElement(x);
        calc(x + 1);
        chosen.remove((Object)x);
        calc(x + 1);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        calc(1);
    }
}
#include<bits/stdc++.h>
using namespace std;
int n;//共计N个数
int m;//选m个数
vector<int> chosen;
string s[1000];
void calc(int x) {
    if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
        return;
    if (x == n + 1) { //选够了m个数输出
        for (int i = 0; i < chosen.size(); i++)
            cout<< s[chosen[i]]<<" ";//也可以不输出，存放起来也是可以的，主要是看题目。
        puts("");
        return;
    }
    chosen.push_back(x);
    calc(x + 1);
    chosen.pop_back();//消除痕迹
    calc(x + 1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    calc(1);
}

大家有个疑虑，我这里全是数字而且是从 11 开始的能好用吗，我题目要是字母怎么办，那么请看下面的题目。

公平抽签

题目描述:

小 A 的学校，蓝桥杯的参赛名额非常有限，只有 �m 个名额，但是共有 �n 个人报名，其中 �≤�m≤n。作为老师非常苦恼，他不知道该让谁去，他在寻求一个绝对公平的方式。于是他准备让大家抽签决定，即 �m 个签是去，剩下的是不去。

小 A 非常想弄明白最后的抽签结果是什么样子的，到底有多少种结果。

请设计一个程序帮助小 A。最后输出各种情况的人名即可，一行一种情况，每种情况的名字按照报名即输入顺序排序。

第一行 输入 �,�N,M。

第二行 到 第 �+1N+1 行 共输入 �N 个人名

每种情况输出 �M 个人名，空格隔开。

样例:

1
2
3
4
5
6
7
8
9
10
11
输入：

3  2
xiaowang
xiaoA
xiaoli
输出：

xiaowang xiaoA
xiaowang xiaoli
xiaoA xiaoli

运行限制:

1
2
1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析：

实际上还是组合型枚举，但是输出元素为人名，我们可以将人名存起来，输出的时候，根据数字下标找到提前存好的人名，直接输出即可。

答案解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
using namespace std;

int n; //共计N个数
int m; //选m个数
vector<string> name;
vector<string> ans;
vector<int> chosen;
void calc(int x)
{

    if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
        return;

    if (x == n + 1)
    { //选够了m个数输出
        string ansTem = "";
        for (int i = 0; i < chosen.size(); i++)
            ansTem += name[chosen[i] - 1] + " ";

        ans.push_back(ansTem);
        return;
    }
    chosen.push_back(x);
    calc(x + 1);

    chosen.pop_back(); //消除痕迹
    calc(x + 1);

}
int main()
{

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        name.push_back(s);
    }
    calc(1);
    for (int i =0; i < ans.size(); i++)
        cout << ans[i] << endl;
}

Python 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
name = []
ans = []
chosen = []
n = 0
m = 0

def calc(x):
    if len(chosen) > m:
        return

    if len(chosen) + n - x + 1 < m:
        return
    if x == n + 1:
        ansTem = ""

        for i in chosen:
            ansTem = ansTem + name[i - 1] + ' '
        # print(ansTem)
        ans.append(ansTem)
        return
    chosen.append(x)
    calc(x + 1)
    chosen.pop()
    calc(x + 1)

if __name__ == '__main__':

    tem = input().split()
    n = int(tem[0])
    m = int(tem[1])
    # print(n," ",m)

    for i in range(n):
        s = input()
        name.append(s)

    # print(name)
    calc(1)

    for i in range(0,len(ans)):
        print(ans[i])

Java 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
import java.util.Vector;

public class Main {

  static  int n;
  static int m;//选m个数
  static Vector<String> name = new Vector<String>();
  static Vector<String> ans = new Vector<String>();
  static Vector<Integer> chosen = new Vector<Integer>();

  static <object> void calc(int x) {

      if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
          return;

      if (x == n + 1) { //选够了m个数输出
          String ansTem = "";
          for (int i = 0; i < chosen.size(); i++)
              ansTem += name.get(chosen.get(i) - 1) + " ";
          ans.addElement(ansTem);
          return;
      }
      chosen.addElement(x);
      calc(x + 1);
      chosen.remove((Object)x);
      calc(x + 1);
  }


  public static void main(String[] args) {

      Scanner in = new Scanner(System.in);
      n = in.nextInt();
      m = in.nextInt();
      for (int i = 0; i < n; i++) {
         String s;
         s=in.next();
         name.addElement(s);
      }
      calc(1);
    for (int i =0; i < ans.size(); i++)
          System.out.println(ans.get(i) );
  }
}

排列型枚举

上面说过，组合型枚举就是让你在 �n 个中，随机选出 �m 个 ，问你有多少种方案，而且每一种方案选择了哪 $m ￥ 个，这就是组合型枚举。

而排列型枚举相对组合型枚举就简单了一点，就是 �n 个的全排列，即从 �n 个中选取 �n 个但是关心内部的顺序。

相比较组合只关心有多少个集合，而排列是关心集合内的排列方式。即排列型枚举就是寻找 ���Ann 问题。

而且排列型枚举也是有着比较成熟的模板需要大家进行记忆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int n; //共计N个数
int order[20];
bool chosen[20];
void calc(int k)
{
    if (k == n + 1)
    {
        for (int i = 1; i <= n; i++)
            cout << order[i] << " ";

        puts("");

        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (chosen[i])
            continue;
        order[k] = i;
        chosen[i] = 1;
        calc(k + 1);
        chosen[i] = 0;
        order[k] = 0;
    }
}
int main()
{
    cin >> n;
    calc(1);
}

Python 写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
order = [0] * 20
chosen = [0] * 20
n = 0
def calc(x):
  if x == n + 1:
      ansTem = ''
      for i in range(1, n + 1):
          print(order[i],end=' ')
      print('')
      return
  for i in range(1,n+1):
      if(chosen[i]==1) :
          continue
      order[x]=i
      chosen[i]=1
      calc(x+1)
      chosen[i]=0
      order[x]=0
if __name__ == '__main__':
  n = int(input())
  # print(name)
  calc(1)

Java 写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static  int n;
static int[] order =new int[20];
static boolean[] chosen =new boolean[20];
static <object> void calc(int x) {
    if (x == n + 1) { //选够了m个数输出
        String ansTem = "";
        for (int i = 1; i <=n ; i++)
            System.out.println(order[i]);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (chosen[i]) continue;
        order[x] = i;
        chosen[i] =true;
        calc(x + 1);
        chosen[i] = false;
        order[x] = 0;
    }
}
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    n = in.nextInt();
    for (int i = 0; i < n; i++) {
       String s;
        s=in.next();
        name.addElement(s);
    }
    calc(1);
}

不少同学问我 2020 够不够，排列问题是阶乘阶的时间复杂度，如果超过这个复杂度，那么这个题也就不用做了，算不出来。

所以肯定够用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

44 的排列就已经这么多了，大家可以尝试跑一下 1010。

同样，我们再来看一个的问题来进行加深理解。

座次问题

题目描述:

小 �A 的学校，老师好不容易解决了蓝桥杯的报名问题，现在老师又犯愁了。现在有 �N 位同学参加比赛，但是老师想给他们排座位，但是排列方式太多了。老师非常想弄明白最后的排座次的结果是什么样子的，到底有多少种结果。

请设计一个程序帮助老师。

最后输出各种情况的人名即可，一行一种情况，每种情况的名字按照报名即输入顺序排序。

第一行 输入 �N； 第二行 到 第 �+1N+1 行 共输入 �N 个人名。

由于小 A 学校承办能力实在有限，所以其中 �N 小于等于 1010 人。

样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：

3
xiaowang
xiaoA
xiaoli
输出：

xiaowang xiaoA xiaoli
xiaowang xiaoli xiaoA
xiaoA xiaowang xiaoli
xiaoA xiaoli xiaowang
xiaoli xiaowang xiaoA
xiaoli xiaoA xiaowang

运行限制:

1
2
1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析：

实际上还是排列型枚举，但是输出元素为人名，我们可以将人名存起来，输出的时候，根据数字下标找到提前存好的人名，就是按照上一道题的方式处理即可。

答案解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using namespace std;

int n; //共计N个数
vector<string> name;
int order[20];
bool chosen[20];
void calc(int k)
{
    if (k == n + 1)
    {
        for (int i = 1; i <= n; i++)
            cout << name[order[i] - 1] << " ";

        puts("");

        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (chosen[i])
            continue;
        order[k] = i;
        chosen[i] = 1;
        calc(k + 1);
        chosen[i] = 0;
        order[k] = 0;
    }
}

int main()
{

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        name.push_back(s);
    }
    calc(1);
}

Python 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
name = []

order = [0] * 20
chosen = [0] * 20
n = 0

def calc(x):

  if x == n + 1:
      ansTem = ''

      for i in range(1, n + 1):
          ansTem = ansTem + name[order[i]-1] + ' '

      print(ansTem)

      return
  for i in range(1,n+1):
      if(chosen[i]==1) :
          continue

      order[x]=i
      chosen[i]=1
      calc(x+1)
      chosen[i]=0
      order[x]=0


if __name__ == '__main__':

  n = int(input())
  for i in range(n):
      s = input()

      name.append(s)

  # print(name)
  calc(1)

Java 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.company;

import java.util.Scanner;
import java.util.Vector;

public class Main {

  static  int n;
  static Vector<String> name = new Vector<String>();
  static int[] order =new int[20];
  static boolean[] chosen =new boolean[20];

  static <object> void calc(int x) {

      if (x == n + 1) { //选够了m个数输出
          String ansTem = "";

          for (int i = 1; i <=n ; i++)

              ansTem += name.get(order[i]-1) + " ";

          System.out.println(ansTem);
          return;
      }

      for (int i = 1; i <= n; i++) {
          if (chosen[i]) continue;
          order[x] = i;
          chosen[i] =true;
          calc(x + 1);
          chosen[i] = false;
          order[x] = 0;
      }
  }

  public static void main(String[] args) {

      Scanner in = new Scanner(System.in);

      n = in.nextInt();

      for (int i = 0; i < n; i++) {

         String s;
          s=in.next();
          name.addElement(s);
      }
      calc(1);
  }
}

尺取法

尺取法（双指针法、two pointers）是一种常用的优化技巧，特别适用于解决序列的区间问题。它的操作简单，易于编程，是一种线性高效的算法。

尺取法的核心思想是维护一个区间（�,�L,R），其中 �L 为起点，�R 为终点，该区间是序列内以 �L 为起点的最短合法区间。关键在于 �R 随着 �L 的增大而增大。通过不断枚举 �L，同时求解相应的 �R，可以高效地解决问题。

具体的实现步骤是，不断移动 �L 指针，同时更新 �R 指针，直到 �R 随着 �L 的增大而增大。因为 �R 随着 �L 的增大而增大，所以总的时间复杂度为 �(�)O(n)。

通过维护两个指针，即左指针 �l 和右指针 �r。通过不断确定区间的左端点，让右指针 �r 不断向右移动，直到满足条件停下，然后维护答案。这个过程重复进行，直到左指针 �l 超过右指针 �r 或满足其他特定情况（根据题目而定）。

尺取法的应用范围广泛，特别适用于需要寻找满足某种条件的连续子序列的问题。通过灵活运用尺取法，可以在保持算法简洁的同时，提高解题效率。

例题 奇怪的的动物园

题目描述

动物园正在展出由世上最受欢迎的 �m 种动物组成的精彩展览。

游客在购买门票时必须说明两个数字，�a 和 �b，代表他们希望观看的展览范围，从第 �a 种动物到第 �b 种动物（包含 �,�a,b）。门票的价格是按照观看的动物数量计算的，即每种动物一元。

小明希望在最小化购票花费的同时，能够欣赏到所有受欢迎的动物。

请计算他应该选择哪些动物范围，即 �a 和 �b。

若存在多组解，输出其中 �a 最小的那组。

输入格式

第一行包含两个整数 �n 和 �m，分别表示动物园内的动物总数以及受欢迎的动物种类数量。

第二行包含 �n 个整数 ��a**i，表示第 �i 种动物的种类。

输出格式

一行包含两个整数 �,�a,b。

样例输入

1
2
12 5
2 5 3 1 3 2 4 1 1 5 4 3

样例输出

1
2 7

思路与算法

这是一道使用尺取法（Two Pointers）的题目。我们维护两个指针 l 和 r，分别表示当前选择区间的左右端点。通过不断调整右指针 r，保证区间内包含所有受欢迎的动物。在滑动窗口的过程中，记录最小购票范围。

具体的实现细节如下：

  1. 使用 I 函数加入第 x 种动物的画，同时更新相应的计数和唯一动物数量。
  2. 使用 D 函数删除第 x 种动物的画，同时更新相应的计数和唯一动物数量。
  3. 不断移动右指针 r，并在保证区间内包含所有受欢迎的动物的前提下，更新最小购票范围。
  4. 移动左指针 l，直到无法再删除动物，保证区间仍然包含所有受欢迎的动物。

复杂度分析

由于每个动物最多被插入和删除一次，算法的时间复杂度为 �(�)O(n)，其中 �n 是动物的数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n, m, a[MAXN], b[MAXN], cnt, ans, ansl, ansr;

// 加入第x种动物
inline void I(int x) {
    if (b[x] == 0) cnt++; // 如果该动物没有在当前区间中出现过，增加唯一动物数量
    b[x]++; // 动物x的数量加1
}

// 删除第x种动物
inline void D(int x) {
    if (b[x] == 1) cnt--; // 如果删除后该动物不再在当前区间中出现，减少唯一动物数量
    b[x]--; // 动物x的数量减1
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // 读取每种动物的种类

    ans = n;
    for (int r = 1, l = 1; r <= n; r++) {
        I(a[r]); // 首先插入a[r]的动物

        while (true) {
            D(a[l]); // 先删a[l]的动物
            if (cnt == m) l++; // 如果删了没事，加l
            else {
                I(a[l]);
                break; // 删了有事，还留着
            }
        }

        if (cnt == m && r - l + 1 < ans) {
            ans = r - l + 1;
            ansl = l;
            ansr = r;
        }
    }

    if (ansl != 0) printf("%d %d", ansl, ansr);
    else printf("1 %d", n); // 输出+特判：选择任意一个≤n的区间不满足要求，则只好选择区间[1,n]

    return 0;
}
MAXN = 1000005
a = [0]*MAXN
b = [0]*MAXN
cnt=0
ansl=0
ansr=0

def I(x):
    global cnt
    if b[x] == 0:
        cnt += 1
    b[x] += 1

def D(x):
    global cnt
    if b[x] == 1:
        cnt -= 1
    b[x] -= 1

n, m = map(int, input().split())
a[1:n+1] = map(int, input().split())

ans = n
l = 1
for r in range(1, n+1):
    I(a[r])
    while True:
        D(a[l])
        if cnt == m:
            l += 1
        else:
            I(a[l])
            break
    if cnt == m and r - l + 1 < ans:
        ans = r - l + 1
        ansl = l
        ansr = r

if ansl != 0:
    print(ansl, ansr)
else:
    print(1, n)
import java.util.Scanner;

public class Main {
    static final int MAXN = 1000005;
    static int[] a ;
    static int[] b;
    static int cnt = 0;

    static void I(int x) {
        if (b[x] == 0) cnt++;
        b[x]++;
    }

    static void D(int x) {
        if (b[x] == 1) cnt--;
        b[x]--;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        a=new int[n+10];
        b=new int[n+10];
        int m = scanner.nextInt();
        for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();

        int ans = n;
        int ansl = 0, ansr = 0;
        for (int r = 1, l = 1; r <= n; r++) {
            I(a[r]);
            while (true) {
                D(a[l]);
                if (cnt == m) l++;
                else {
                    I(a[l]);
                    break;
                }
            }
            if (cnt == m && r - l + 1 < ans) {
                ans = r - l + 1;
                ansl = l;
                ansr = r;
            }
        }

        if (ansl != 0) System.out.println(ansl + " " + ansr);
        else System.out.println("1 " + n);
    }
}

这个算法通过维护两个指针，实现了在 �(�)O(n) 的时间复杂度内找到最小购票范围的目标。尺取法的思想在滑动窗口的过程中，通过不断调整左右指针来满足特定条件。

≡