题目描述

给出数轴上坐标从小到大的 $R$ 个点，坐标范围在 $1\sim L$ 之间。选出一段连续的点，满足：存在一个点，使得所有选出的点到其距离和不超过 $B$ 。求最多能够选出多少点。

$R\le 10^5,L\le 10^9,B\le 2\times 10^{15}$

输入

第一行 三个整数 R L B

接下来R行 每行一个整数 表示X[i]

输出

一个整数 最多稻米数

样例输入

5 20 6

1

2

10

12

14

样例输出

3

---

题解

双指针法

傻题，显然对于一段连续的点，使得距离和最小的点是它们的中位数。

于是使用双指针法，用前缀和求距离和即可。

时间复杂度 $O(n)$ 

#include 
     
      typedef long long ll;ll a[100010] , sum[100010];int main(){    int n , i , mid , p = 1 , ans = 0;    ll m , k;    scanf("%d%lld%lld" , &n , &m , &k);    for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &a[i]) , sum[i] = sum[i - 1] + a[i];    for(i = 1 ; i <= n ; i ++ )    {        while(p <= n && (mid = (p + i) >> 1 , sum[p] - sum[mid] - a[mid] * (p - mid)) + (a[mid] * (mid - i + 1) - sum[mid] + sum[i - 1]) <= k) p ++ ;        if(ans < p - i) ans = p - i;    }    printf("%d\n" , ans);    return 0;}