subsequence 尺取法

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int arr[1000010];  
 7 
 8 int main()
 9 {
10     int T,n,S;  
11     scanf("%d",&T);
12     while(T--)
13     {
14         scanf("%d%d",&n,&S);
15         for(int i=0;i<n;i++)
16             scanf("%d",arr+i);
17         int s=0,t=0,sum=0,res=n+1;
18         for(;;)
19         {
20             while(t<n&&sum<S)
21                 sum+=arr[t++];
22             if(sum<S)
23                 break;
24             res=min(res,t-s);
25             sum-=arr[s];
26             s++;
27         }
28         if(res>n)
29             res=0;
30         printf("%d
",res);
31     }
32     return 0;
33 }
34             
35

View Code

我们假设以arrs开始总和最初大于S时的连续子序列为arrs+...+arrt-1，这时arrs-1+...+arrt-2<arrs+...+arrt-2<arrs+...+arrt-1成立

利用这个性质可以设计如算法；

(1) 以s=t=sum=0初始化；

(2)只有依然有sum<S时，就不段将sum增加arri，将t加1；

(3)如果(2)中无法满足sum<S则终止。否则的话，更新res；

(4)就sum减去arrs，s增加1然后回到（2）中；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int arr[100010];  
 7 int sum[100010];
 8 int main()
 9 {
10     int T,n,S;  
11     scanf("%d",&T);
12     while(T--)
13     {
14         scanf("%d%d",&n,&S);
15         sum[0]=0;
16         for(int i=0;i<n;i++)
17         {
18             scanf("%d",arr+i);
19             sum[i+1]=sum[i]+arr[i];
20         }
21         if(sum[n]<S)
22         {
23             printf("0
");
24             continue;
25         }
26         int res=n;
27         for(int s=0;sum[s]+S<=sum[n];s++)
28         {
29             int t=lower_bound(sum+s,sum+n,sum[s]+S)-sum;
30             res=min(res,t-s);
31         }
32         printf("%d
",res);
33     }
34     return 0;
35 }
36             
37

View Code

先预处理下，在用二分法查找一遍，时间复杂度为nlogn，能通过。