#P3829. 第1题-超市备货检查
-
1000ms
Tried: 150
Accepted: 43
Difficulty: 5
所属公司 :
京东
时间 :2025年9月27日
-
算法标签>双指针
第1题-超市备货检查
解题思路
题意:给定长度为 n 的货位序列,每个位置放一种商品(编号从 1 开始)。再给出 m 个要求数组 b[1..m],表示第 x 类商品在区间内至少出现 bx 次。求满足所有要求的最短连续区间长度,不存在则输出 -1。
核心算法:双指针滑动窗口
-
只关心 bx>0 的品类,其余视为无需约束。
-
先做一次可行性预检:统计整段序列每个品类的总次数
total[x],若存在total[x] < b[x](且b[x]>0),则必无解,直接输出 -1。 -
使用左右指针维护当前窗口
[l, r],并用cnt[x]统计窗口内每个品类出现次数。- 右指针右移扩张窗口,若某类第一次达到需求(
cnt[x]==b[x]且b[x]>0),则把“已满足的品类数”sat加一。 - 当
sat等于“需要的品类数”needKinds时,尝试左移l贪心缩小:只要移走左端商品不会让该类小于需求(cnt[a[l]]-1 >= b[a[l]]),就移动并更新计数。记录最小长度。
- 右指针右移扩张窗口,若某类第一次达到需求(
-
特判:如果所有 bx=0,任意单点即可,答案为 1。
实现要点
- 计数数组大小取
max(m, max(a)),对编号超过m的商品,将其需求视为 0。 - 维护变量:
needKinds(有正需求的品类数)、sat(当前满足的品类数)、ans(最小长度)。
复杂度分析
- 时间复杂度:O(n+m)。每个指针最多走一遍;预检一次遍历。
- 空间复杂度:O(K),其中 K=max(m,max(a))(计数与需求数组)。
代码实现
Python
# 题面功能在函数中,输入输出在主函数(ACM风格)
import sys
def shortest_interval(n, m, arr, need_input):
# 计算编号上界,容纳可能大于 m 的商品编号
max_id = max(max(arr), m)
need = [0] * (max_id + 1)
for i in range(1, m + 1):
need[i] = need_input[i - 1]
# 预检:整段统计
total = [0] * (max_id + 1)
for x in arr:
if x <= max_id:
total[x] += 1
for i in range(1, max_id + 1):
if need[i] > 0 and total[i] < need[i]:
return -1
# 需要的品类数
needKinds = sum(1 for i in range(1, max_id + 1) if need[i] > 0)
if needKinds == 0:
return 1 # 任意一个位置即可
cnt = [0] * (max_id + 1)
sat = 0
ans = n + 1
l = 0
for r in range(n):
x = arr[r]
cnt[x] += 1
# 刚好达到需求时,已满足品类 +1(只对 b[x] > 0 生效)
if need[x] > 0 and cnt[x] == need[x]:
sat += 1
# 已满足所有需求,尝试收缩左端
while sat == needKinds:
# 更新答案
curr_len = r - l + 1
if curr_len < ans:
ans = curr_len
# 能否安全移走左端?
y = arr[l]
if cnt[y] - 1 >= need[y]:
cnt[y] -= 1
l += 1
else:
break
# 若仍满足,继续移走左端元素(确保最短)
while sat == needKinds:
y = arr[l]
if cnt[y] - 1 >= need[y]:
cnt[y] -= 1
l += 1
ans = min(ans, r - l + 1)
else:
break
# 若移走会破坏需求,则等待下次扩张
if sat == needKinds:
# 尝试移走一次并更新 sat
y = arr[l]
cnt[y] -= 1
l += 1
if need[y] > 0 and cnt[y] == need[y] - 1:
sat -= 1
return -1 if ans == n + 1 else ans
def main():
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
arr = [int(next(it)) for _ in range(n)]
need_input = [int(next(it)) for _ in range(m)]
print(shortest_interval(n, m, arr, need_input))
if __name__ == "__main__":
main()
Java
// 类名必须为 Main,ACM 风格:主函数做输入输出,功能在外部静态函数
import java.io.*;
import java.util.*;
public class Main {
// 快读(数据量较大时更稳)
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, x = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
return x * sgn;
}
}
// 题面功能实现:返回最短长度,不存在返回 -1
static int shortestInterval(int n, int m, int[] arr, int[] needIn) {
int maxId = m;
for (int x : arr) if (x > maxId) maxId = x;
int[] need = new int[maxId + 1];
for (int i = 1; i <= m; i++) need[i] = needIn[i - 1];
// 预检:整段统计
int[] total = new int[maxId + 1];
for (int x : arr) total[x]++;
for (int i = 1; i <= maxId; i++) {
if (need[i] > 0 && total[i] < need[i]) return -1;
}
int needKinds = 0;
for (int i = 1; i <= maxId; i++) if (need[i] > 0) needKinds++;
if (needKinds == 0) return 1;
int[] cnt = new int[maxId + 1];
int sat = 0, ans = n + 1;
int l = 0;
for (int r = 0; r < n; r++) {
int x = arr[r];
cnt[x]++;
if (need[x] > 0 && cnt[x] == need[x]) sat++;
while (sat == needKinds) {
ans = Math.min(ans, r - l + 1);
int y = arr[l];
if (cnt[y] - 1 >= need[y]) {
cnt[y]--;
l++;
} else {
break;
}
}
if (sat == needKinds) {
int y = arr[l];
cnt[y]--;
l++;
if (need[y] > 0 && cnt[y] == need[y] - 1) sat--;
}
}
return ans == n + 1 ? -1 : ans;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt(), m = fs.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = fs.nextInt();
int[] need = new int[m];
for (int i = 0; i < m; i++) need[i] = fs.nextInt();
int ans = shortestInterval(n, m, arr, need);
System.out.println(ans);
}
}
C++
// ACM 风格:主函数读写,核心功能放在外部函数
#include <bits/stdc++.h>
using namespace std;
// 返回最短区间长度,不存在返回 -1
int shortestInterval(int n, int m, const vector<int>& a, const vector<int>& needIn) {
int maxId = m;
for (int x : a) maxId = max(maxId, x);
vector<int> need(maxId + 1, 0);
for (int i = 1; i <= m; ++i) need[i] = needIn[i - 1];
// 预检:整段统计
vector<int> total(maxId + 1, 0);
for (int x : a) total[x]++;
for (int i = 1; i <= maxId; ++i) {
if (need[i] > 0 && total[i] < need[i]) return -1;
}
int needKinds = 0;
for (int i = 1; i <= maxId; ++i) if (need[i] > 0) needKinds++;
if (needKinds == 0) return 1;
vector<int> cnt(maxId + 1, 0);
int sat = 0, ans = n + 1;
int l = 0;
for (int r = 0; r < n; ++r) {
int x = a[r];
cnt[x]++;
if (need[x] > 0 && cnt[x] == need[x]) sat++;
// 收缩左端,尽可能短
while (sat == needKinds) {
ans = min(ans, r - l + 1);
int y = a[l];
if (cnt[y] - 1 >= need[y]) {
cnt[y]--;
l++;
} else break;
}
// 若仍满足,尝试移走一个以继续扩展
if (sat == needKinds) {
int y = a[l];
cnt[y]--;
l++;
if (need[y] > 0 && cnt[y] == need[y] - 1) sat--;
}
}
return (ans == n + 1) ? -1 : ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> need(m);
for (int i = 0; i < m; ++i) cin >> need[i];
cout << shortestInterval(n, m, a, need) << "\n";
return 0;
}
题目内容
某超市要对一批货架上的商品进行备货检查。货架上共有 n 个连续的货位(编号 1 到 n ),每个货位上放置着一种商品。当前超市有 m 类商品(编号 1 到 m ),其中第 x 类商品要求在检查区间内至少出现 bx 次 (bx 为非负整数)。
请找出长度最短的连续货位区间 [l,r] ,使得该区间内 1 到 m 类商品的出现次数均满足上述要求。我们定义区间长度为 r−l+1 。若不存在这样的区间,输出 −1 。
输入描述
第一行包含两个整数 n 和 m(1≤n,m≤105) ,分别表示货位总数和商品的类别数。
第二行包含 n 个整数,依次表示每个货位上的商品编号。
第三行包含 m 个整数,依次表示第 1 到 m 类商品的最低出现次数要求( b1 到 bm ) 。
保证商品编号为不超过 105 的非负整数。
输出描述
输出一个整数,表示满足要求的最短区间长度;
若不存在,输出 −1 。
样例1
输入
10 4
3 1 2 1 3 4 2 1 3 2
2 1 0 1
输出
5
说明
重点监拉的 4 类商品要求:
商品 1 :至少出现 2 次;
商品 2 :至少出现 1 次;
商品 3 :至少出现 0 次(无要求);
商品 4 :至少出现 1 次。
其中一种符合要求的最短区间是 [4,8] (商品序列为 [1,3,4,2,1],长度为 5 。