当前位置：首页 > article >正文

区间问题【前缀和】

article 2024/11/5 11:31:47

前缀和数组：用于处理连续多次取区间和操作的情况，取区间和期间不能对原数组进行区间增减数操作

1. 求前缀和数组

假定原数组arr，前缀和数组prefixArr，当前讨论位置为i
那么有prefixArr[i]=arr[i]+arr[i-1]+arr[i-2]+…+arr[0]（即i位置及之前所有数累加和==>前缀和）
由于prefixArr[i-1]=arr[i-1]+arr[i-2]+…+arr[0]
因此化简原式：prefixArr[i]=prefixArr[i-1]+arr[i]

2. 求区间和

设求[i,j]（j>i）区间的区间和即求arr[i]+arr[i+1]+…+arr[j-1]+arr[j] 由于prefixArr[j]=arr[j]+arr[j-1]+arr[j-2]+…arr[0]，prefixArr[i-1]=arr[i-1]+arr[i-2]+arr[i-3]+…+arr[0]
因此所求区间和为prefixArr[j]-prefixArr[i-1]

代码如下

 
public class PrefixArr {
    public static void main(String[] args) {
        //获取数组
        int[] arr = getArr(10);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        //前缀数组
        int[] prefixArr = new int[arr.length];
        prefixArr[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefixArr[i] = prefixArr[i - 1] + arr[i];
        }
        //获取[i,j]区间的数
        int i = 3;
        int j = 5;
        int ijNum = prefixArr[j] - prefixArr[i - 1];
        System.out.println("ijNum: " + ijNum);
    }
 
    private static int[] getArr(int len) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 9 + 1);
        }
        return arr;
    }
}

实战案例

Thanh 想在一面被均分为 N
 段的墙上画一幅精美的壁画。

每段墙面都有一个美观评分，这表示它的美观程度（如果它的上面有画的话）。

不幸的是，由于洪水泛滥，墙体开始崩溃，所以他需要加快他的作画进度！

每天 Thanh 可以绘制一段墙体。

在第一天，他可以自由的选择任意一段墙面进行绘制。

在接下来的每一天，他只能选择与绘制完成的墙面相邻的墙段进行作画，因为他不想分开壁画。

在每天结束时，一段未被涂颜料的墙将被摧毁（Thanh 使用的是防水涂料，因此涂漆的部分不能被破坏），且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。

Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。

Thanh想要保证，无论墙壁是如何被摧毁的，他都可以达到至少 B
 的美观总分。

请问他能够保证达到的美观总分 B
 的最大值是多少。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据的第一行包含整数 N
。

第二行包含一个长度为 N
 的字符串，字符串由数字 0∼9
 构成，第 i
 个字符表示第 i
 段墙面被上色后能达到的美观评分。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x
 为组别编号（从 1
 开始），y
 为 Thanh 可以保证达到的美观评分的最大值。

数据范围
1≤T≤100
,
存在一个测试点N=5∗106
,其他测试点均满足2≤N≤100

输入样例：
4
4
1332
4
9583
3
616
10
1029384756
输出样例：
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
样例解释
在第一个样例中，无论墙壁如何被破坏，Thanh都可以获得 6
 分的美观总分。在第一天，他可以随便选一个美观评分3的墙段进行绘画。在一天结束时，第一部分或第四部分将被摧毁，但无论哪一部分都无关紧要。在第二天，他都可以在另一段美观评分 3
 的墙段上作画。

在第二个样例中，Thanh 在第一天选择最左边的美观评分为 9
 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体，因为最左边的墙壁被涂上了颜料。在第二天，他可以选择在左数第二段评分为 5
 的墙面上作画。然后右数第二段墙体被摧毁。请注意，在第二天，Thanh不能选择绘制第三段墙面，因为它不与任何其他作画墙面相邻。这样可以获得 14
 分的美观总分。

https://www.acwing.com/problem/content/564/

package acwin;

import java.util.Arrays;
import java.util.Scanner;

public class acwin562 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试用例数量
        for (int t = 1; t <= T; t++) {
            int N = scanner.nextInt(); // 读取墙面数量
            String str = scanner.next(); // 读取墙面美观评分字符串
            int[] s = new int[N + 1]; // 初始化前缀和数组
//          计算前缀和数组
            for (int i=1;i<=N;i++){
                s[i]=s[i-1]+str.charAt(i-1)-'0';
            }
            int m = (N+1)/2;
            int res=0;
            for (int i = m; i <= N; i++) {
                System.out.println(s[i]);
                System.out.println(s[i-m]);
                //根据题目要求是s[i-m]就是被摧毁的墙壁。
                
                res = Math.max(res, s[i] - s[i - m]);
            }
            System.out.println(res);
        }
    }
}