MENU

Hands that shed innocent blood

March 23, 2019 • Read: 209 • 算法

最容易想到的思路就是从左往右遍历,遍历的过程中,如果当前剑长不等于0,就从当前位置往左,把剑长范围内的人都+1,表示被砍到1次。时间复杂度$O(n^2)$

上面的解法很明显会超时,正确解法应该是线段树,或者差分加前缀和

如果用线段树做就是裸题,没什么好说的,这里说一下用差分加前缀和的做法

首先定义差分数组$d$,初始值全部为0,差分的性质是可以将区间修改改为单点修改,例如要将$[L,R]$区间内所有值加上$C$,相当于将差分数组中$d[L]+=C$以及$d[R+1]-=C$。差分还有一个性质是:差分序列的前缀和等于原始数组,利用这两个性质,我们就可以快速统计出整个区间每个人被砍过的次数

具体做法是,遍历剑长数组,如果不为0,就将$d[max(0,i - arr[i])]+=1$以及$d[max(0, i - 1) + 1] -= 1$

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        long[] arr = new long[n]; // 原始数组
        long[] d = new long[n]; // 差分序列
        long[] life = new long[n]; // 生命值
        for (int i = 0; i < n; i++) {
            arr[i] = cin.nextInt();
            if (arr[i] != 0) { // 剑长不等于0才修改差分序列
                d[(int) Math.max(0, i - arr[i])] += 1; // d[L] += 1
                d[Math.max(i - 1, 0) + 1] -= 1; // d[R + 1] -= 1
            }
        }
        for (int i = 0; i < n; i++)
            life[i] = cin.nextInt();
        
        long ans = d[0] >= life[0] ? 1 : 0; // 因为差分序列的第一个值就是原始序列,所以第一个值直接结算
        for (int i = 1; i < n - 1; i++) { // 最后一个人不用考虑,因为没有人砍他
            d[i] += d[i - 1]; // 前缀和
            ans += (d[i] > life[i] ? 1 : 0);
        }
        System.out.println(n - ans);
    }
}
最后编辑于: March 29, 2019
Archives Tip
QR Code for this page
Tipping QR Code