当前位置：首页 > news >正文

题解：AtCoder AT_awc0003_d Consecutive Practice Days

news 2026/4/24 22:35:07

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Consecutive Practice Days

【题目描述】

Takahashi is the manager of the track and field club, and he manages the practice records of the club members.
高桥是田径俱乐部的经理，负责管理俱乐部会员的练习记录。

The track and field club has a practice period ofN NNdays, and each day is numbered from1 11toN NN. On dayi ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N), a positive integerA i A_iAirepresenting the “practice intensity” for that day is recorded.
田径俱乐部的练习期为N NN天，每天从1 11到N NN编号。在第i ii天（1 ≤ i ≤ N 1 ≤ i ≤ N1≤i≤N），记录了一个表示当天"练习强度"的正整数A i A_iAi。

According to the club’s rules, a period consisting ofr − l + 1 r - l + 1r−l+1consecutive days from dayl llto dayr rris called an “achievement period” and is specially recognized if its length is at leastK KKdays and the total practice intensity within the period is at least the target valueM MM.
根据俱乐部规定，由第l ll天到第r rr天的连续r − l + 1 r-l+1r−l+1天组成的时间段称为"成就期"，如果其长度至少为K KK天且该时间段内的总练习强度至少达到目标值M MM，则会被特别认可。

Takahashi wants to find out how many achievement periods qualify for recognition.
高桥想知道有多少个成就期符合认可条件。

Specifically, find the number of integer pairs( l , r ) (l, r)(l,r)that satisfy all of the following conditions:
具体而言，求满足以下所有条件的整数对( l , r ) (l, r)(l,r)的数量：

1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N
r − l + 1 ≥ K r - l + 1 \geq Kr−l+1≥K(the length of the period is at leastK KKdays)
A l + A l + 1 + ⋯ + A r ≥ M A_l + A_{l+1} + \cdots + A_r \geq MAl+Al+1+⋯+Ar≥M(the total practice intensity within the period is at leastM MM)

【输入】

N NNK KKM MM
A 1 A_1A1A 2 A_2A2⋯ \cdots⋯A N A_NAN

The first line contains an integerN NNrepresenting the number of days in the practice period, an integerK KKrepresenting the minimum length of a period, and an integerM MMrepresenting the target value for the total practice intensity, separated by spaces.
The second line containsN NNintegersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting the practice intensity for each day, separated by spaces.

【输出】

Print the number of integer pairs( l , r ) (l, r)(l,r)that satisfy the conditions, on a single line.

【输入样例】

5 2 10 3 5 4 2 6

【输出样例】

【解题思路】

【算法标签】

#前缀和#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,k,m,ans;// n: 数组长度，k: 最小长度，m: 目标和inta[N],sa[N];// a: 原始数组，sa: 前缀和数组signedmain(){cin>>n>>k>>m;// 读入数组长度、最小长度和目标总和for(inti=1;i<=n;i++){cin>>a[i];// 读入数组元素sa[i]=sa[i-1]+a[i];// 计算前缀和}// 双指针算法，计算满足条件的子数组数量for(inti=1,j=1;i<=n;i++)// i为子数组左端点{// 移动右端点j，直到找到满足条件的子数组while(j<=n&&(sa[j]-sa[i-1]<m||j-i+1<k)){j++;}// 调试输出// cout << "i j " << i << " " << j << endl;// 如果找到了满足条件的子数组，计算以i为左端点的子数组个数// 从j到n的所有位置都可以作为右端点ans+=(n-j+1);}cout<<ans<<endl;// 输出满足条件的子数组个数return0;}