Yet Another Monster Fight
Problem - D - Codeforces
題目大意：
現在給你一堆怪物，你擁有法術（一個法術可以連續攻擊這n個所有怪物），你可以選擇任意一個怪物作為法術的第一個攻擊目標（傷害為x），然后除了第一個攻擊目標可以任意，其他攻擊目標只能為曾經攻擊目標的相鄰怪物。然后傷害依次遞減，x x-1 x-2 ......如果傷害大于等于怪物的血量，則怪物被擊殺。
現在你第一次攻擊目標一定是最優的，問你最壞情況下，x需要多少才能一次法術把所有怪物擊殺完畢。?
思路解析：（紅色的為正確思路）
因為只能攻擊曾經攻擊過的相鄰怪物。則攻擊第i個怪物，你應該攻擊過第i-1個怪物，或者第i+1個怪物，最壞情況下應該是 前i-1個怪物全部攻擊過和 第i個怪物之后（不包括第i個怪物）都攻擊過。所以我們應該枚舉那個怪物為最開始的攻擊目標，然后在每個怪物作為開始的攻擊目標的最壞情況下求最好情況，則就是我們需要的答案。
但是我比賽的時候傻了，我沒想到枚舉，我以為以最大值作為開始攻擊目標一定是最好的，因為樣例是這樣的。（但是有可能出現不是的情況）。
如果以7作為第一次的攻擊目標，答案為12， 但是以藍色的6作為第一次的攻擊目標答案為11.
代碼實現：
import java.util.ArrayList;
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex22* @author:HWJ* @Data: 2023/11/24 23:16*/
public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int max = 0;ArrayList<Integer> list = new ArrayList<>();int n = input.nextInt();int[] arr = new int[n];int[] a = new int[n];int[] b = new int[n];int[] c = new int[n + 1];int ans = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {arr[i] = input.nextInt();a[i] = arr[i] + i;b[i] = arr[i] + n - i - 1;}c[n] = 0;for (int i = n - 1; i > 0; i--) {c[i] = Math.max(c[i + 1], a[i]);}int cur = 0;for (int i = 0; i < n; i++) {if(i > 0){cur = Math.max(cur, b[i - 1]);}int res = Math.max(cur, c[i + 1]);res = Math.max(res, arr[i]);ans = Math.min(res, ans);}System.out.println(ans);}}
)
