由于购买的土地必须是连续的,不难想到维护费用使用前缀和即可。然后只需要通过二分查找去找从 $i$ 开始买土地最多能买到哪一块。假设是 $j(1\le i\le j\le n)$ ,那么其对答案的贡献就是 $j-i+1$ 。 一共做 $n$ 次二分查找,所以复杂度是 $O(n\log n)$ (这里提供一个C语言手写的上界二分查找,对应 C++ 当中的 upper_bound
)
#include <stdio.h>
int n, m, ans;
int s[10010];
int upper_bound(int a[], int lo, int hi, int val)
{
if (val >= a[hi])
return hi + 1;
int mi = 0;
while (lo < hi)
{
mi = (lo + hi) >> 1;
if (a[mi] <= val) lo = mi + 1;
else hi = mi;
}
return lo;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &s[i]), s[i] += s[i - 1];
for (int i = 1; i <= n; ++i)
ans += upper_bound(s, i, n, m + s[i - 1]) - i;
printf("%d", ans);
}