#P3850. 第4题-大鱼吃小鱼
-
1000ms
Tried: 16
Accepted: 5
Difficulty: 7
所属公司 :
拼多多
时间 :2025年9月28日
-
算法标签>单调栈二分
第4题-大鱼吃小鱼
解题思路
-
核心转化 要让第
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))
-
计算前缀和
ps[0..n](ps[0]=0),由于a_i>0,ps严格递增。 -
预处理
Lsame与Rsame。 -
对每个
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 条鱼的血量记为 ai 。
该游戏有以下规则:一条鱼只有在它的血量严格大于(不包含等于)它相邻的鱼时,它才能吃掉这条相邻的鱼,并且增加自身血量,增加值等于被吃掉的鱼的血量。如果没有任何一条鱼的血量严格大于它的邻居,则游戏结束。
例如,有 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<=105)
第 2 行包含 n 个正整数: a1,a2,...,an(1<=n<=105),表示每条鱼的血量。
测试样例中 n 条鱼的血量之和不会超过 1010 。
输出描述
共 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