【尺取】POJ 3320-白红宇

【尺取】POJ 3320

阅读量：6824 次

发布时间：2019-06-26

本文共 642 字，大约阅读时间需要 2 分钟。

题意：一本书P页，第i页有ai知识点，问你至少从某一处开始连续要翻多少页才能复习完所有的知识点，不能跨页翻。

思路：《挑战程序设计》上的尺取法的经典例题，set用来求出所有不重复知识点的个数，map用来计算是否有新出现的的知识点。

1.左端点s，右端点t，目前复习的知识点num初始化为0；

2.只要有t < P，num < n，且出现新的知识点counts[a[t++]]++==0，num++；

3.如果num < n，则无法解决该题。否则更新答案，min(res,t-s);

4.从s开始缩小范围，若某一知识点的次数为零，则num–；回归2.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;const int maxn = 1000000+10;int P;int a[maxn];int main(){ while(~scanf("%d",&P)){ set
           
             all; for(int i=0;i
            
              counts; int res = P; for(;;){ while(t

转载于:https://www.cnblogs.com/MIKORU/p/5796742.html

你可能感兴趣的文章