解题思路

• 核心转化 要让第 i 条鱼被吃掉，必须先在它一侧（左或右）“造”出一个紧邻它、血量严格大于 a_i 的块。造块的方式就是同侧若干条相邻鱼互相吞吃并合并为一个块（每次由较大者吃较小者）。 若这侧最终用到 m 条鱼把它们合成一个块再吃掉 i，总操作次数就是：块内合并 m-1 次 + 最后吃 i 的 1 次，共 m 次。因此，对每个 i，答案是左右两侧中能达到 sum > a_i 的最短相邻窗口长度的最小值（若两侧都不行则为 -1）。

• 关键细节：严格大于与“全相等”窗口 所有血量为正数，因此同侧窗口长度随扩展单调增加，最短超过 a_i 的窗口可用前缀和 + 二分直接定位。 但若该窗口长度 m≥2 且窗口内元素全相等，则它们互相都不是“严格大于”，无法发生任何一次吞吃，不能被合并成块。此时必须再把窗口再向外扩 1 个不同值进入窗口，窗口才可合并。 为了 O(1) 判断“是否全相等”，预处理相等段：

  • Lsame[i]：以 i 结尾的相等段的最左端位置；
  • Rsame[i]：以 i 开始的相等段的最右端位置。 对于以 i-1 结尾的左窗口 [l..i-1]，当且仅当 l ≥ Lsame[i-1] 且 m≥2 时为“全相等”；右侧同理：若最短右窗口 [i+1..r] 满足 r ≤ Rsame[i+1] 且 m≥2，则“全相等”。这两种情况都把窗口再各向外扩到 Lsame[i-1]-1 或 Rsame[i+1]+1（若存在），即可保证含有不同值，且和更大，满足可合并。

• 实现方法（整体 O(n log n)）

  1. 计算前缀和 ps[0..n]（ps[0]=0），由于 a_i>0，ps 严格递增。

  2. 预处理 Lsame 与 Rsame。

  3. 对每个 i：

     • 左侧：若 ps[i-1] > a_i，用二分找最短使 ps[i-1]-ps[l-1] > a_i 的窗口起点 等价于 l = lower_bound(ps[0..i-1], ps[i-1] - a_i)，窗口长度 m = i - l。 若 m≥2 且 l ≥ Lsame[i-1]，把 l 改为 Lsame[i-1]-1（若 >0），长度随之更新；若 Lsame[i-1]==1 则左侧无解。
     • 右侧：若 ps[n]-ps[i] > a_i，用二分找最短使 ps[r]-ps[i] > a_i 的窗口终点 等价于 r = upper_bound(ps[0..n], ps[i] + a_i)，窗口长度 m = r - i。 若 m≥2 且 r ≤ Rsame[i+1]，把 r 改为 Rsame[i+1]+1（若 ≤n），长度随之更新；若 Rsame[i+1]==n 则右侧无解。
     • 取左右可行长度的最小值作为答案；两侧都不可行则为 -1。

• 正确性要点

  • 只要窗口内存在至少一处相邻不等，就一定能通过“让当前更大的块不断吃相邻较小块”的顺序把整个窗口合并成一个块（例如从一个全局最大元素处开始向两侧扩张）。
  • 唯一不可合并的情形是窗口内长度 ≥2 且全相等；本题用相等段扩 1 个不同值即可规避。

复杂度分析

• 前缀和与相等段预处理：O(n) 时间、O(n) 空间。
• 每个位置做常数次二分：O(log n)，总计 O(n log n)。
• 额外空间：O(n)（数组与前缀和）。

代码实现

Python

# 题意：求每条鱼被吃掉的最少操作次数；若不可能则 -1
# 方法：前缀和 + 二分 + 相等段修正（避免全相等窗口）
import sys
from bisect import bisect_left, bisect_right

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    n = data[0]
    a = [0] * (n + 1)  # 1-based
    for i in range(1, n + 1):
        a[i] = data[i]

    # 前缀和 ps[0..n]
    ps = [0] * (n + 1)
    for i in range(1, n + 1):
        ps[i] = ps[i - 1] + a[i]

    # 相等段边界
    Lsame = [0] * (n + 1)
    Rsame = [0] * (n + 2)
    Lsame[1] = 1
    for i in range(2, n + 1):
        if a[i] == a[i - 1]:
            Lsame[i] = Lsame[i - 1]
        else:
            Lsame[i] = i
    Rsame[n] = n
    for i in range(n - 1, 0, -1):
        if a[i] == a[i + 1]:
            Rsame[i] = Rsame[i + 1]
        else:
            Rsame[i] = i

    INF = 10**9
    ans = [INF] * (n + 1)

    for i in range(1, n + 1):
        best = INF

        # 向左侧合并
        if i > 1 and ps[i - 1] > a[i]:
            target = ps[i - 1] - a[i]
            # 在 ps[0..i-1] 上做 lower_bound
            r = bisect_left(ps, target, 0, i)
            l = r
            m = i - l
            # 相等段修正：若窗口长度 >=2 且完全落在与 a[i-1] 相等的段里，需扩到段外
            if m >= 2 and l >= Lsame[i - 1]:
                if Lsame[i - 1] > 1:
                    l2 = Lsame[i - 1] - 1
                    m = i - l2
                else:
                    m = INF
            best = min(best, m)

        # 向右侧合并
        if i < n and (ps[n] - ps[i] > a[i]):
            target = ps[i] + a[i]
            # 在 ps[0..n] 上做 upper_bound
            r = bisect_right(ps, target, 0, n + 1)
            m = r - i
            # 相等段修正：若窗口长度 >=2 且完全落在与 a[i+1] 相等的段里，需扩到段外
            if m >= 2 and r <= Rsame[i + 1]:
                if Rsame[i + 1] < n:
                    r2 = Rsame[i + 1] + 1
                    m = r2 - i
                else:
                    m = INF
            best = min(best, m)

        ans[i] = -1 if best >= INF else best

    print(' '.join(str(ans[i]) for i in range(1, n + 1)))

if __name__ == "__main__":
    main()

Java

// 题意：对每条鱼，求其被吃掉的最少操作次数；不能被吃掉则 -1
// 方法：前缀和 + 二分 + 相等段修正（避免全相等窗口）
import java.io.*;
import java.util.*;

public class Main {
    // 在 ps[l..r]（闭区间）上做 lower_bound：返回最小下标 idx 使 ps[idx] >= target
    static int lowerBound(long[] ps, int l, int r, long target) {
        int left = l, right = r;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (ps[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    // 在 ps[l..r]（闭区间）上做 upper_bound：返回最小下标 idx 使 ps[idx] > target
    static int upperBound(long[] ps, int l, int r, long target) {
        int left = l, right = r;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (ps[mid] > target) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    public static void main(String[] args) throws Exception {
        // 根据数据范围使用 BufferedReader + StringTokenizer
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] parts = br.readLine().trim().split("\\s+");
        long[] a = new long[n + 1]; // 1-based
        for (int i = 1; i <= n; i++) a[i] = Long.parseLong(parts[i - 1]);

        // 前缀和
        long[] ps = new long[n + 1];
        for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];

        // 相等段
        int[] Lsame = new int[n + 1];
        int[] Rsame = new int[n + 2];
        Lsame[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] == a[i - 1]) Lsame[i] = Lsame[i - 1];
            else Lsame[i] = i;
        }
        Rsame[n] = n;
        for (int i = n - 1; i >= 1; i--) {
            if (a[i] == a[i + 1]) Rsame[i] = Rsame[i + 1];
            else Rsame[i] = i;
        }

        final int INF = 1_000_000_000;
        int[] ans = new int[n + 1];
        Arrays.fill(ans, INF);

        for (int i = 1; i <= n; i++) {
            int best = INF;

            // 左侧
            if (i > 1 && ps[i - 1] > a[i]) {
                long target = ps[i - 1] - a[i];
                int r = lowerBound(ps, 0, i - 1, target); // ps[r] >= target
                int l = r; // l = r
                int m = i - l; // 初始最短长度
                if (m >= 2 && l >= Lsame[i - 1]) {
                    if (Lsame[i - 1] > 1) {
                        int l2 = Lsame[i - 1] - 1;
                        m = i - l2;
                    } else {
                        m = INF;
                    }
                }
                best = Math.min(best, m);
            }

            // 右侧
            if (i < n && (ps[n] - ps[i] > a[i])) {
                long target = ps[i] + a[i];
                int r = upperBound(ps, 0, n, target); // ps[r] > target
                int m = r - i;
                if (m >= 2 && r <= Rsame[i + 1]) {
                    if (Rsame[i + 1] < n) {
                        int r2 = Rsame[i + 1] + 1;
                        m = r2 - i;
                    } else {
                        m = INF;
                    }
                }
                best = Math.min(best, m);
            }

            ans[i] = (best >= INF) ? -1 : best;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
}

C++

// 题意：求每条鱼被吃掉的最少操作次数；若不可能则 -1
// 方法：前缀和 + 二分 + 相等段修正（避免全相等窗口）
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n + 1, 0); // 1-based
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 前缀和
    vector<long long> ps(n + 1, 0);
    for (int i = 1; i <= n; ++i) ps[i] = ps[i - 1] + a[i];

    // 相等段
    vector<int> Lsame(n + 1, 0), Rsame(n + 2, 0);
    Lsame[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] == a[i - 1]) Lsame[i] = Lsame[i - 1];
        else Lsame[i] = i;
    }
    Rsame[n] = n;
    for (int i = n - 1; i >= 1; --i) {
        if (a[i] == a[i + 1]) Rsame[i] = Rsame[i + 1];
        else Rsame[i] = i;
    }

    const int INF = 1e9;
    vector<int> ans(n + 1, INF);

    for (int i = 1; i <= n; ++i) {
        int best = INF;

        // 左侧
        if (i > 1 && ps[i - 1] > a[i]) {
            long long target = ps[i - 1] - a[i];
            // lower_bound 在 ps[0..i-1]
            int r = int(lower_bound(ps.begin(), ps.begin() + i, target) - ps.begin());
            int l = r;
            int m = i - l;
            if (m >= 2 && l >= Lsame[i - 1]) {
                if (Lsame[i - 1] > 1) {
                    int l2 = Lsame[i - 1] - 1;
                    m = i - l2;
                } else {
                    m = INF;
                }
            }
            best = min(best, m);
        }

        // 右侧
        if (i < n && (ps[n] - ps[i] > a[i])) {
            long long target = ps[i] + a[i];
            // upper_bound 在 ps[0..n]
            int r = int(upper_bound(ps.begin(), ps.end(), target) - ps.begin());
            int m = r - i;
            if (m >= 2 && r <= Rsame[i + 1]) {
                if (Rsame[i + 1] < n) {
                    int r2 = Rsame[i + 1] + 1;
                    m = r2 - i;
                } else {
                    m = INF;
                }
            }
            best = min(best, m);
        }

        ans[i] = (best >= INF) ? -1 : best;
    }

    // 输出
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

题目内容

多多在玩大鱼吃小鱼的游戏，目前有 $n$ 条鱼，编号从 $1$ 到 $n$ 按顺序排列，第 $i$ 条鱼的血量记为 $a_i$ 。

该游戏有以下规则：一条鱼只有在它的血量严格大于(不包含等于)它相邻的鱼时，它才能吃掉这条相邻的鱼，并且增加自身血量，增加值等于被吃掉的鱼的血量。如果没有任何一条鱼的血量严格大于它的邻居，则游戏结束。

例如，有 $n=5，a=[2,2,3,1,4]$ 。该过程可能如下进行：

首先，第 $3$ 条鱼吃掉第 $2$ 条鱼。第 $3$ 条鱼的血量变为 $5$ ，第 $2$ 条鱼被吃掉。

然后，第 $3$ 条鱼吃掉第 $1$ 条鱼(由于第 $2$ 条鱼已被吃掉，他们现在是相邻的)。第 $3$ 条鱼的血量变为 $7$ ，第 $1$ 条鱼被吃掉。

接着，第 $5$ 条鱼吃掉第 $4$ 条鱼。第 $5$ 条鱼的血量变为 $5$，第 $4$ 条鱼被吃掉。

最后，第 $3$ 条鱼吃掉第 $5$ 条鱼(由于第 $4$ 条鱼已被吃掉，他们现在是相邻的)。第 $3$ 条鱼的血量变为 $12$ ，第 $5$ 条鱼被吃掉。

请问：对于每一条鱼，计算在所有可能的进食顺序中，它被其他鱼吃掉所需的最少次数是多少？如果它不可能被吃掉，则输出 $-1$ 。

输入描述

共 $2$ 行，第一行包含一个正整数 $n$ ，表示鱼的数量。$(1<=n<=10^5)$

第 $2$ 行包含 $n$ 个正整数: $a_1,a_2,...,a_n(1<=n<=10^5)$，表示每条鱼的血量。

测试样例中 $n$ 条鱼的血量之和不会超过 $10^{10}$ 。

输出描述

共 $1$ 行，每行输出 $n$ 个整数。第 $i$ 个整数表示第 $i$ 条鱼被其他鱼吃掉所需的最少次数；

如果不可能被吃掉，则输出 $-1$ 。

样例1

输入

4
3 2 4 2

输出

2 1 2 1

样例2

输入

3
1 2 3

输出

1 1 -1

样例3

输入

5
2 2 3 1 1

输出

2 1 -1 1 2