北京信息科技大学第十三届程序设计竞赛暨ACM选拔赛 A题题解

瞎bb

这题在现场想到了贪心部分，也想到了优化要用到线段树/树状数组。时间不太够我
码了，就直接放弃思考了，现在看来当时想的思路是正确的，码一下树状数组说不定
能过2。赛后补题，思路代码几乎都对了，然后一个小细节给我绕进去了，卡了半
天，好歹最后和lzh讨论了一下，改了一个参数过了233，标程是差分数组，我采用了
线段树的做法。

题解

前置知识：树状数组，差分

贪心部分

1.从左开始遍历，遍历到第一个大于1（即需要跳跃的蹦床）则在这个蹦床开始跳一定是
最优解
证明：设开始跳的蹦床为第i个，左侧的所有蹦床都为1，右侧的未知，从右侧任何一个
蹦床开始跳跃都无法对第i个蹦床产生贡献，左侧的任何一个蹦床开始跳，最终都会达到
第i个蹦床，且费用一定是1，因此从第i个蹦床开始跳跃一定为最优解（当然从左侧第一
个开始跳也最优解，不过这样难以实现）

2.计a[i]为原第i个蹦床的弹力值，c[i]为从左侧跳到第i个蹦床的次数。
情况1：如果a[i]>1，则一定从a[i]个蹦床往后跳a[i]-1次，且对[i+2,i+a[i]]的蹦床产生一个1的贡献，
情况2：如果a[i]-c[i]<1，则表示i蹦床弹力值到1后仍进行了c[i]-a[i]-1次跳跃，且这些贡献只会出现在c[i+1]中（这里卡了我好久，把自己绕进了对[i+1,n]产生贡献里）。
情况3：只有遍历到i个蹦床且a[i]-c[i]>1时才需要选择i为起点进行跳跃。

数据结构部分

理解了上述贪心部分数据结构部分则很简单了，问题已经抽象为区间修改和单点查询。用
树状数组或者线段树直接莽过去（线段树赛后补题实测会t，比赛时提交是否能ac不清楚）。

代码

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

//a数组是原数组，c是树状数组。
int kase , n , a[5100] , c[5100];
inline int lowbit(int x){
    return x & (-x);
}
void add(int pos , int x){
    while (pos <= n) c[pos] += x , pos += lowbit(pos);
}
int query(int pos){
    int res = 0;
    while (pos > 0) res += c[pos] , pos -= lowbit(pos);
    return res;
}

int main() {
    scanf("%d", &kase);
    while (kase--) {
        memset(a, 0, sizeof a);
        memset(c, 0, sizeof c);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = query(i);
            if (a[i] - tmp > 1) {
                //情况3
                res += a[i] - tmp - 1;
            } else if (a[i] - tmp < 1) {
                //情况2
                add(i + 1, -(a[i] - tmp) + 1);
                add(i + 2, -(-(a[i] - tmp) + 1));
            }
            if (a[i] > 1) {
                //情况1
                add(i + 2, 1);
                add(min(i + a[i] + 1, n + 1), -1);
            }
        }
        printf("%lld\n", res);
    }
}