Somnia1337

用户名：dotcpp0729277

访问量：1304

签　名：

等　　级
排　　名	12774
经　　验	955
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

砍柴 - 预处理 & 记忆化搜索
浏览：309

你可能喜欢

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

回文数组 - 贪心

　　作者: Somnia1337　　　　发表时间：2024-04-18 09:30:25 浏览：281　|　评论：0　

原题链接：蓝桥杯2024年第十五届省赛真题-回文数组

#### 解题思路

操作：

1. 选择一个元素，对其增减 1
2. 选择相邻的两个元素，对其增减 1

双指针 `i`、`j` 从两端向中间看，每次先用“操作 1”使 `arr[i] == arr[j]`，然后看 `arr[i+1]` 和 `arr[j-1]` 是否与它们同号，如果同号，可以将一部分操作改为“操作 2”，从而节约操作次数。

实现时，可以先一次遍历，更新 `arr[i] -= arr[j]`，再次遍历时仅比较 `arr[i]` 和 `arr[i+1]` 是否同号即可。

#### 答案

```java
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 预处理
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            arr[i] -= arr[j];
        }
        
        // 遍历前一半
        long ans = 0;
        for (int i = 0; i < n / 2; i++) {
            if (arr[i] == 0) continue;
            // 先用 "操作 1" 变 arr[i]
            ans += Math.abs(arr[i]);
            // 再看能否顺便变一下 arr[i+1]
            if (i + 1 < n / 2 && arr[i] > 0 == arr[i + 1] > 0) {
                arr[i + 1] = Math.abs(arr[i]) > Math.abs(arr[i + 1]) ? 0 : arr[i + 1] - arr[i];
            }
        }
        out.println(ans);
        
        out.flush();
        out.close();
    }
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Somnia1337

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

回文数字（C++代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

回文数组 - 贪心

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1013题解

1118（求助_已解决）

printf基础练习2 （C语言代码）

GC的苦恼（C语言代码）

钟神赛车（C语言代码）

Somnia1337

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

回文数字 （C++代码）

C二级辅导-同因查找 （C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

回文数组 - 贪心

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1013题解

1118（求助_已解决）

printf基础练习2 （C语言代码）

GC的苦恼 （C语言代码）

钟神赛车 （C语言代码）

回文数字（C++代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

　　评论区

GC的苦恼（C语言代码）

钟神赛车（C语言代码）