尺取法 poj3061 poj3320-白红宇

尺取法 poj3061 poj3320

阅读量：5323 次

发布时间：2019-06-14

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

尺取法就是反复推进区间的开头和结尾，来求满足条件的最下区间。

poj3061 http://poj.org/problem?id=3061

给定一个都是正整数的序列，要我们求总和不小于S的连续子序列的长度的最小值

如果序列是总和最迟大于S的连续子序列

那么

所以只有加上，从开始的连续子序列才有可能大于S

所以从开始的总和最初大于S的连续子序列是则一定有

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 #pragma warning(disable:4996)15 typedef long long LL;16 #define cinInt(a) scanf("%d",&a)17 #define cinInt64(a) scanf("%I64d",&a)18 #define cinDouble(a) scanf("%lf",&a)19 const int INF = 1 << 30;20 const int N = 100000 + 10;21 int a[N];22 void input(int &x)23 {24 char ch = getchar();25 while(ch>'9' || ch<'0')26 ch = getchar();27 x = 0;28 while(ch>='0' && ch<='9')29 {30 x = x * 10 + ch - '0';31 ch = getchar();32 }33 }34 int main()35 {36 int n,S,i;37 int t;38 scanf("%d",&t);39 while(t--)40 {41 scanf("%d%d",&n,&S);42 for(i=0; i

View Code

poj3320 http://poj.org/problem?id=3320

给我们一本p页的书，每页有一个知识点ai, 全书中同一个知识点可能会被多次提到，问我们最少读多少页连续的书。

如果区间[s,t]覆盖了所有的知识点，那么区间[s+1,t'] t'>=t , 所以可以用尺取法，即使用尺取法的条件是但区间的开头递增时，区间的结尾一定是不减的。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 #pragma warning(disable:4996)15 typedef long long LL;16 #define cinInt(a) scanf("%d",&a)17 #define cinInt64(a) scanf("%I64d",&a)18 #define cinDouble(a) scanf("%lf",&a)19 const int INF = 1 << 30;20 void input(int &x)21 {22 char ch = getchar();23 while(ch>'9' || ch<'0')24 ch = getchar();25 x = 0;26 while(ch>='0' && ch<='9')27 {28 x = x * 10 + ch - '0';29 ch = getchar();30 }31 }32 map
                  
                    vis;33 int a[10000000+10];34 int main()35 {36 int n,i;37 int cnt = 0;38 while(scanf("%d",&n)!=EOF)39 {40 for(i=0; i

View Code

转载于:https://www.cnblogs.com/justPassBy/p/4505118.html

你可能感兴趣的文章