AcWing 531. 铺设道路
原题链接
中等
#pragma GCC optimize(3)
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, tr[N], sum, t;
int lowbit(int x)
{
return x & -x;
}
void update(int x, int c) // 位置x加c
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int query(int x) // 返回前x个数的和
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
int d;
scanf("%d", &d);
update(i, d);
}
while (true) {
for (int i = t; i <= n; i ++ ) {
if (query(i)) {
t = i;
break;
} else t ++ ;
}
if (t > n) break;
int y = t;
for (int i = t + 1; i <= n; i ++ )
if (query(i) == query(i - 1)) {
y = i - 1;
break;
} else y ++ ;
for (int i = t; i <= y; i ++ )
update(i, -1);
sum ++ ;
}
printf("%lld", sum);
}