HDU 5806

题意:说统计一个长度为n的字符串中至少有k个大于等于m的数的字串的个数。

思路:尺取法!!如果已经统计过的数中有k个数是不小于m的,那么后面再加上任意数,这个区间都符合要求。想通了这一点,这道题便好做了。 一发AC

#include<bits/stdc++.h>
#define maxn 200003
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
int a[maxn];

int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k,m;
		cin>>n>>m>>k;
		for(int i=0;i<n;i++){
			scanf("%d",a+i);
		}
		int l=0,r=0,num=0; LL ans=0;
        while(1)
        {
            while(num<k&&r<n) if(a[r++]>=m) num++;
            if(num<k) break;
            ans+=n-r+1;
            if(a[l]>=m) num--;
            l++;
        }
        printf("%lld\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用递归解决猴子吃桃问题

    用户7727433
  • 湖南大学程序设计竞赛新生赛(重现赛)

    题目链接—点我开启传送门哦! A.题意:就是求任意两个斐波那契数列的最大公约数!

    用户7727433
  • 2019年安徽大学ACM/ICPC实验室新生赛

    A.素数分布函数\pi (n)π(n)表示小于或等于n的素数的数目。例如\pi (10)=4π(10)=4(2,3,5,7是素数)。这个函数涉及到许多高等数论的...

    用户7727433
  • 2018年全国多校算法寒假训练营练习比赛(第一场)六子冲

     棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)与被攻方的1个棋子皆处在一条直线上并相邻时,被攻方的这个棋子就被消灭  每次移动后判断一下,移动后...

    mathor
  • 汽水瓶问题(非常interesting)

    输入文件最多包含10组测试数据,每个数据占一行,仅包含一个正整数n(1<=n<=100),表示小张手上的空汽水瓶数。n=0表示输入结束,你的程序不应当处理这一行

    用户7656790
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • hdu 5249 KPI 权值线段树裸题

    用户2965768
  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • 算24

    解题思路: n个数算24,必有两个数要先算。这两个数算的结果,和剩余n-2个数,就构成了n-1个数求24的问题。枚举先算的两个数,以及这两个数的运算方式。n...

    AI那点小事
  • LintCode 二进制中有多少个1题目分析

    这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制...

    desperate633

扫码关注云+社区

领取腾讯云代金券