题解：P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2

_MiyazonoKaori_ · 2025-02-06 10:08:31 · 题解

upd:

2025.11.22：二分的时间复杂度写错了，感谢 @complete_binary_tree 指出。

@yuruilin2026 和@Hootime 两个大佬认为这是道水题，一眼秒了。

1. 二分（31pts）

二分初始力量值，从题目知道力量初始值 x 范围为 0\le x \le 10^9，时间复杂度则为 O(N^2 \times \log(10^9))，但题目中 N 的范围为 2 \le N \le 5 \times 10^5，所以极端情况过不了。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fast_gets ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open_f_same freopen("data.in", "r", stdin);freopen("data.out", "w", stdout);
#define close_f fclose(stdin);fclose(stdout);
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
inline void write(int x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int a[514514],b[514514];
int n;
bool cheek(int x){
    for(int start=0;start<n;start++){
        int fight=x;
        bool flag=true;
        for(int i=0;i<n;i++){
            int j=(i+start)%n;
            if(fight<a[j]){
                flag=false;
                break;
            }
            fight+=b[j];
        }
        if(flag==true) return true;
    }
    return false;
}
int main(){
    //fast_gets
    //open_f_same
    n=read();
    for(int i=0;i<n;i++) a[i]=read();
    for(int i=0;i<n;i++) b[i]=read();
    int low=0,hight=1000000000;
    int ans;
    while(low<=hight){
        int mid=(low+hight)/2;
        if(cheek(mid)){
            ans=mid;
            hight=mid-1;
        }else{
            low=mid+1;
        }
    }
    write(ans);
    //close_f
    return 0;
}

2. 加入前缀和预处理和预处理最大值数组

1. 策略：

• 比太郎选择一个起始点 j，按 j,j+1,…,N 的顺序打怪，再回头打 1,2,…,j−1 的怪物。
• 需要确保在每一步中，比太郎的力量都足够打败当前的怪物。

  2. 优化思路：

• 使用前缀和快速计算区间和。
• 预处理最大值数组，快速查询后续部分和前部分的最小需求。
• 遍历每个起始点，计算对应的最小初始力量需求，并找到所有起始点中的最小值。

  3. 代码

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; ++i) cin >> A[i];
  for (int i = 0; i < N; ++i) cin >> B[i];
  vector<ll> pre_sum(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
      pre_sum[i] = pre_sum[i - 1] + B[i - 1];
  }
  vector<ll> left_max(N + 2, LLONG_MIN);
  left_max[N + 1] = LLONG_MIN;
  for (int j = N; j >= 1; --j) {
      ll current = A[j - 1] - pre_sum[j - 1];
      left_max[j] = max(current, left_max[j + 1]);
  }
  vector<ll> right_max(N + 2, LLONG_MIN);
  ll fight = LLONG_MIN;
  for (int i = 1; i <= N; ++i) {
      ll temp = A[i - 1] - pre_sum[i - 1];
      if (temp > fight) {
          fight = temp;
      }
      right_max[i + 1] = fight;
  }
  ll min_x = LLONG_MAX;
  for (int j = 1; j <= N; ++j) {
      ll sum_j_minus_1 = pre_sum[j - 1];
      ll max1 = sum_j_minus_1 + left_max[j];
      ll sum_b_part = pre_sum[N] - sum_j_minus_1;
      ll max2 = (j > 1) ? (right_max[j] - sum_b_part) : LLONG_MIN;
      ll x_j = max(max1, max2);
      if (x_j < min_x) {
          min_x = x_j;
      }
  }
  cout << min_x << endl;
  return 0;
  }

4. 代码解释

• 前缀和预处理：
  1. pre_sum 数组用于快速计算区间和。
  2. left_max 数组：从后往前遍历，计算每个位置到末尾的最大值，用于后续部分的最小力量需求。
  3. right_max 数组：从前往后遍历，维护当前最大值，用于前部分的最小力量需求。
• 遍历每个起始点：
  1. 计算每个起始点对应的最小初始力量需求，并找到所有起始点中的最小值。

该算法的时间复杂度为 O(N)。