尺取法(挑战程序设计竞赛)

清疚 2022-12-28 12:45 210阅读 0赞

### 文章目录 ###

*  尺取法
 *   *  例题1
     *   *  题目描述
         *  输入描述
         *  输出描述
         *  输入
         *  输出
         *  算法分析
         *  解题代码
     *  例题2
     *   *  题目描述
         *  输入描述
         *  输出描述
         *  输入
         *  输出
         *  算法分析
         *  代码

--------------------

# 尺取法 #

尺取法一般用于求子序列的和、乘积等，给遍历求权值以一个更低的时间复杂度的方法。

**反复地推进区间的开头和结尾，来求取满足条件的最小区间的方法**

## 例题1 ##

### 题目描述 ###

给出了**N**个正整数序列\*\*(10 < N < 100,000)**，每个正整数小于或等于**10000\*\*，一个正整数**S (S < 100 000 000)**。编写一个程序，求序列中连续元素的子序列的最小长度，其和大于或等于**S**。

### 输入描述 ###

> 第一行是测试用例的数量。对于每个测试用例，程序都必须读取从第一行开始的数字**N**和**S**，它们之间用间隔隔开。序列的编号在测试用例的第二行给出，用间隔隔开。输入将在文件结束时结束。

### 输出描述 ###

> 对于每种情况，程序都必须在输出文件的单独行上打印结果。如果没有回答，打印0。

### 输入 ###

2
    10 15
    5 1 3 5 10 7 4 9 2 8
    5 11
    1 2 3 4 5

### 输出 ###

2
    3

### 算法分析 ###

![1][] ![2][] ![3][]

### 解题代码 ###

void solve()
    {
        
      int res = n + 1;
      int s = 0, t = 0, sum = 0;
      
      for(;;){
        
        while(t < n && sum < S)
          sum += a[t++];	//尾加
        
        if(sum < S)	//如果0～n的sum都比S小，那就不存在解
          break;
        res = min(res, t - s);
        sum -= a[s++];	//头减
      }
      
      if(res > n)
        //解不存在
        res = 0;
      
      printf("%d\n", res);
    }

## 例题2 ##

### 题目描述 ###

杰西卡是一个非常可爱的女孩，很多男孩都在追求她。最近她有个问题。期末考试就要到了，但她还没怎么花时间。如果她想通过考试，她必须掌握一本厚厚的教科书中包含的所有内容。那本教科书的作者，和其他作者一样，对知识点非常挑剔，因此有些知识点被多次提及。杰西卡认为如果她能把每个知识点至少读一遍，她就能通过考试。她决定只阅读书中一个连续的部分，其中包含了整本书涵盖的所有知识点。当然，子目录应该尽可能的薄。

一个非常勤奋的男孩为她手工索引了杰西卡课本的每一页，并告诉了她每一页的知识点，这对他的求爱来说是一个很大的进步。你是来拯救杰西卡的，请给出索引，帮助杰西卡决定她应该读哪个相邻的部分。为了方便起见，每个想法都被编码了一个ID，它是一个非负整数。

### 输入描述 ###

> 输入的第一行是整数**P(1 ≤ P ≤ 1000000)**，即Jessica的课本页数。第二行包含**P**个非负整数，描述每页的内容。第一个整数是第一页的内容，第二个整数是第二页的内容，以此类推。您可以假设出现的所有整数都能很好地适合有符号32位整数类型。

### 输出描述 ###

> 输出一行：书中最短连续部分的页数，包含了书中所有的知识点。

### 输入 ###

> 5  
> 1 8 8 8 1

### 输出 ###

> 2

### 算法分析 ###

![4][]

### 代码 ###

#include <iostream>
    #include <cstdio>
    #include <map>
    #include <set>
    using namespace std;
    
    int p;
    int a[1000005];
    map<int, int> ln;	//记录每个知识点出现了多少次，知识->出现次数的映射
    set<int> all;	//统计知识点的总数
    int main()
    {
        
        cin >> p;
        
        int cnt = 0;
        for(int i = 0; i < p; i++){
        
            scanf("%d", &a[i]);
            all.insert(a[i]);
        }
        
        cnt = (int)all.size();
        
      	//尺取法
        int e = 0,s = 0;
        int ans = p;
        int res = 0;
        for(;;){
        
            while(e < p && res != cnt){
        
                if(ln[a[e]] == 0)
                    res++;	//如果一个知识点新出现，那么总共学的知识点数增加
                ln[a[e]]++;
                e++;
            }
            if(res != cnt)
                break;
            ans = min(ans, e - s);
            ln[a[s]]--;	//头删除，将该知识点出现次数减1
            if(!ln[a[s]]) //如果知识点减为0，就说明这个知识点未出现
                res--;
            s++;
        }
      	//尺取法
        
        printf("%d\n", ans);
        
        return 0;
    }

[1]: https://s1.ax1x.com/2020/03/17/8aQpCQ.jpg
[2]: https://s1.ax1x.com/2020/03/17/8aMz4g.jpg
[3]: /images/20221120/0bdaa3b19f014d29ac4645feb28b4745.png
[4]: https://s1.ax1x.com/2020/03/17/8aMvE8.jpg