题意:给出一个序列,问能找出多少个连续的子序列,使得这个子序列中第k大的数字不小于m。
分析:这个子序列中只要大于等于m的个数大于等于k个即可。那么,我们可以用尺取法写,代码不难写,但是有些小细节需要注意(见代码注释)。我觉得,《挑战程序设计》里的尺取法的内容需要好好的再回顾一下= =。
代码如下:
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 typedef long long ll; 6 const int N = 200000 + 5; 7 8 int a[N]; 9 10 int main() 11 { 12 int T;scanf("%d",&T); 13 while(T--) 14 { 15 int n,m,k;scanf("%d%d%d",&n,&m,&k); 16 for(int i=1;i<=n;i++) scanf("%d",a+i); 17 int s = 1, t = 1, num = 0; 18 ll ans = 0; 19 for(;;) 20 { 21 while(num<k && t<=n) 22 { 23 if(a[t++] >= m) 24 { 25 num++; 26 } 27 } 28 //if(t>n) break; 29 if(num < k) break; 30 // 必须采取下面的写法,不然会WA 31 // 因为可能即使 t>n 出来此时刚好也 num==k 了,必须再加一次。 32 // 也可以为了保险,在下面这个语句前面加上 if(num >= k) 33 ans += n-t+2; 34 if(a[s++] >= m) num--; 35 } 36 printf("%I64d ",ans); 37 } 38 }
———————————————————2017.1.18分界线———————————————————————
又做了一遍这题,上面的说法是错误的,循环退出的条件应该是起点s>n而不是终点t>n。而上面num<k的写法正确是因为,num<k此时t肯定>n才退出里面的循环,而终点不变,起点一直前进说明范围一直减少,num只会更少,因此再也不可能出现num>=k的情况,所以可以直接退出了。但是直接判断s来判断循环是否结束是肯定没有错的(虽然时间上可能会差一点,但还是O(n)的)。
重写的代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 200000 + 5; 4 typedef long long ll; 5 6 int a[N]; 7 int T,n,k,m; 8 9 int main() 10 { 11 scanf("%d",&T); 12 while(T--) 13 { 14 scanf("%d%d%d",&n,&m,&k); 15 for(int i=1;i<=n;i++) scanf("%d",a+i); 16 int s = 1, t = 1; 17 int num = 0; 18 ll ans = 0; 19 while(1) 20 { 21 while(num < k && t <= n) 22 { 23 if(a[t++] >= m) num++; 24 } 25 if(num >= k) ans += n - (t-1) + 1; 26 if(a[s++] >= m) num--; 27 if(s == n + 1) break; 28 } 29 printf("%I64d ",ans); 30 } 31 return 0; 32 }