拼多多校招笔试真题 10.26 - 货物免检批次(C++/Py/Java /Js/Go)

货物免检批次

拼多多 10月26号 笔试真题 第三题

拼多多真题目录点击查看: 拼多多笔试真题题库目录｜笔试题库 + 算法考点详解

题目内容

多多的冷链仓库里，传送带上依次摆着

M

M

M 件还没查过的货。从左往右数，第

i

i

i 件的检查耗时是

P

i

P_i

Pi​，它要走的档位是

G

i

G_i

Gi​，只可能是

0

0

0 或

1

1

1。 多多得挑出一段中间不间断、至少含一件的货，并按它们原来的先后把这一段查完。刚开查时，排在最前面的那件要哪个档位，设备就先停在哪个档位；往后只要紧挨着的两件档位不一样，就得再花

S

S

S 的时间把设备拨过去。 同一段里最多能用一次免检。免检盖住这一段内部连续的至多

W

W

W 件货，被盖住的检查耗时改成

0

0

0。这些货仍留在原位过机器，该用的档位一个都不改，该付的拨动时间也照付。 请算出总耗时不超过

U

U

U 时，这一段最长能有多少件货。

输入描述

首行四个整数

M

,

W

,

U

,

S

M,W,U,S

M,W,U,S（

1

≤

M

≤

2

×

10

5

,

1

≤

W

≤

M

,

0

≤

U

≤

10

18

,

0

≤

S

≤

10

9

1 \\le M \\le 2 \\times 10^5,1 \\le W \\le M,0 \\le U \\le 10^{18},0 \\le S \\le 10^9

1≤M≤2×105,1≤W≤M,0≤U≤1018,0≤S≤109），空格隔开，依次是货有多少件、一次免检最多连续盖住几件、这一段允许的耗时上限、每拨一次档位要花的时间。 第二行

M

M

M 个整数

P

1

,

P

2

,

…

,

P

M

P_1,P_2,\\dots,P_M

P1​,P2​,…,PM​（

1

≤

P

i

≤

10

9

1 \\le P_i \\le 10^9

1≤Pi​≤109），空格隔开，是每件货的检查耗时。 第三行

M

M

M 个整数

G

1

,

G

2

,

…

,

G

M

G_1,G_2,\\dots,G_M

G1​,G2​,…,GM​（

G

i

∈

{

0

,

1

}

,

1

≤

i

≤

M

G_i \\in \\{0,1\\},1 \\le i \\le M

Gi​∈{0,1},1≤i≤M），空格隔开，是每件货要的档位。

输出描述

写出一个整数，表示耗时不超过

U

U

U 时，最长的那一段有多少件货。

样例1

输入

5 1 6 3
2 4 1 5 2
0 0 0 1 1

输出

3

说明 取最左边三件。检查耗时

2

+

4

+

1

=

7

2+4+1=7

2+4+1=7，免检只能盖住

1

1

1 件，盖住中间的

4

4

4 之后还剩

3

3

3。三件档位都是

0

0

0，不用拨设备。总耗时

3

3

3，没有超过

6

6

6。再多拿一件就会超过

6

6

6。

样例2

输入

4 2 5 4
3 8 3 9
1 0 0 1

输出

2

说明 取中间两件

8

8

8 和

3

3

3。两件都能被免检盖住，档位都是

0

0

0，总耗时是

0

0

0。任意连续三件都要留下一件的检查耗时，再加上一次拨档的

4

4

4，都会超过

5

5

5。

题解

思路

解题思路: 二分 + 滑动窗口 + 单调队列 + 前缀和

C++

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int M, W;
ll U, S;
cin >> M >> W >> U >> S;
// 检查耗时
vector<ll> P(M + 1, 0);
vector<int> G(M + 1);
// 前缀和
vector<ll> sum(M + 1, 0);
// 切换挡位次数前缀和
vector<int> change(M + 1, 0);

for (int i = 1; i <= M; i++) {
cin >> P[i];
sum[i] = sum[i – 1] + P[i];
}

for (int i = 1; i <= M; i++) {
cin >> G[i];
change[i] = change[i – 1];

if (i >= 2 && G[i] != G[i – 1]) {
change[i]++;
}
}

// q[i] 表示从第 i 件开始，连续 W 件货物的检查耗时
int n = M – W + 1;
vector<ll> q(n + 1, 0);

for (int i = 1; i <= n; i++) {
q[i] = sum[i + W – 1] – sum[i – 1];
}

// 判断是否存在长度为 len 的合法区间
auto check = [&](int len) -> bool {
// 整段都可以免检，只需要考虑档位切换耗时
if (len < W) {
for (int l = 1; l + len – 1 <= M; l++) {
int r = l + len – 1;
ll cost = 1LL * S * (change[r] – change[l]);

if (cost <= U) {
return true;
}
}
return false;
}

// 单调递减队列，维护 q 中长度为 len-W+1 的窗口最大值
deque<int> dq;
int window = len – W + 1;

for (int i = 1; i <= n; i++) {
// 保持队列中的 q 值单调递减
while (!dq.empty() && q[dq.back()] <= q[i]) {
dq.pop_back();
}
dq.push_back(i);

// 移除不属于当前窗口的下标
while (!dq.empty() && dq.front() <= i – window) {
dq.pop_front();
}

// 当前已经形成一个完整的窗口
if (i >= window) {
int l = i – window + 1;
int r = l + len – 1;

// 原始检查耗时
ll total = sum[r] – sum[l – 1];

// 最优免检收益
ll saved = q[dq.front()];

// 档位切换耗时
ll switching = 1LL * S * (change[r] – change[l]);

if (total – saved + switching <= U) {
return true;
}
}
}

return false;
};

// 二分最长合法区间长度
int left = 1, right = M, ans = 0;

while (left <= right) {
int mid = left + (right – left) / 2;

if (check(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid – 1;
}
}

cout << ans << '\\n';

return 0;
}

java

import java.util.*;

public class Main {
static int M, W;
static long U, S;
static long[] sum, q;
static int[] G, change;

// 判断是否存在长度为 len 的合法区间
static boolean check(int len) {
// 整段都可以免检，只需要考虑档位切换耗时
if (len < W) {
for (int l = 1; l + len – 1 <= M; l++) {
int r = l + len – 1;
long cost = S * (change[r] – change[l]);

if (cost <= U) {
return true;
}
}
return false;
}

// 单调递减队列，维护 q 中长度为 len-W+1 的窗口最大值
Deque<Integer> dq = new ArrayDeque<>();
int n = M – W + 1;
int window = len – W + 1;

for (int i = 1; i <= n; i++) {
// 保持队列中的 q 值单调递减
while (!dq.isEmpty() && q[dq.peekLast()] <= q[i]) {
dq.pollLast();
}
dq.offerLast(i);

// 移除不属于当前窗口的下标
while (!dq.isEmpty() && dq.peekFirst() <= i – window) {
dq.pollFirst();
}

// 当前已经形成一个完整的窗口
if (i >= window) {
int l = i – window + 1;
int r = l + len – 1;

// 原始检查耗时
long total = sum[r] – sum[l – 1];

// 最优免检收益
long saved = q[dq.peekFirst()];

// 档位切换耗时
long switching = S * (change[r] – change[l]);

if (total – saved + switching <= U) {
return true;
}
}
}

return false;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

M = sc.nextInt();
W = sc.nextInt();
U = sc.nextLong();
S = sc.nextLong();

// 检查耗时
long[] P = new long[M + 1];
G = new int[M + 1];

// 前缀和
sum = new long[M + 1];

// 切换档位次数前缀和
change = new int[M + 1];

for (int i = 1; i <= M; i++) {
P[i] = sc.nextLong();
sum[i] = sum[i – 1] + P[i];
}

for (int i = 1; i <= M; i++) {
G[i] = sc.nextInt();
change[i] = change[i – 1];

if (i >= 2 && G[i] != G[i – 1]) {
change[i]++;
}
}

// q[i] 表示从第 i 件开始，连续 W 件货物的检查耗时
int n = M – W + 1;
q = new long[n + 1];

for (int i = 1; i <= n; i++) {
q[i] = sum[i + W – 1] – sum[i – 1];
}

// 二分最长合法区间长度
int left = 1, right = M, ans = 0;

while (left <= right) {
int mid = left + (right – left) / 2;

if (check(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid – 1;
}
}

System.out.println(ans);
sc.close();
}
}

python

from collections import deque

M, W, U, S = map(int, input().split())

# 检查耗时
P = [0] + list(map(int, input().split()))
G = [0] + list(map(int, input().split()))

# 前缀和
sum_ = [0] * (M + 1)

for i in range(1, M + 1):
sum_[i] = sum_[i – 1] + P[i]

# 切换档位次数前缀和
change = [0] * (M + 1)

for i in range(1, M + 1):
change[i] = change[i – 1]

if i >= 2 and G[i] != G[i – 1]:
change[i] += 1

# q[i] 表示从第 i 件开始，连续 W 件货物的检查耗时
n = M – W + 1
q = [0] * (n + 1)

for i in range(1, n + 1):
q[i] = sum_[i + W – 1] – sum_[i – 1]

# 判断是否存在长度为 length 的合法区间
def check(length):
# 整段都可以免检，只需要考虑档位切换耗时
if length < W:
for l in range(1, M – length + 2):
r = l + length – 1
cost = S * (change[r] – change[l])

if cost <= U:
return True

return False

# 单调递减队列，维护 q 中长度为 length-W+1 的窗口最大值
dq = deque()
window = length – W + 1

for i in range(1, n + 1):
# 保持队列中的 q 值单调递减
while dq and q[dq[–1]] <= q[i]:
dq.pop()

dq.append(i)

# 移除不属于当前窗口的下标
while dq and dq[0] <= i – window:
dq.popleft()

# 当前已经形成一个完整的窗口
if i >= window:
l = i – window + 1
r = l + length – 1

# 原始检查耗时
total = sum_[r] – sum_[l – 1]

# 最优免检收益
saved = q[dq[0]]

# 档位切换耗时
switching = S * (change[r] – change[l])

if total – saved + switching <= U:
return True

return False

# 二分最长合法区间长度
left, right, ans = 1, M, 0

while left <= right:
mid = left + (right – left) // 2

if check(mid):
ans = mid
left = mid + 1
else:
right = mid – 1

print(ans)

Go

package main

import (
"bufio"
"fmt"
"os"
)

var M, W int
var U, S int64
var sum, q []int64
var G, change []int

// 判断是否存在长度为 len 的合法区间
func check(length int) bool {
// 整段都可以免检，只需要考虑档位切换耗时
if length < W {
for l := 1; l+length–1 <= M; l++ {
r := l + length – 1
cost := S * int64(change[r]–change[l])

if cost <= U {
return true
}
}
return false
}

// 单调递减队列，维护 q 中长度为 length-W+1 的窗口最大值
n := M – W + 1
dq := make([]int, n+1)
head, tail := 0, 0
window := length – W + 1

for i := 1; i <= n; i++ {
// 保持队列中的 q 值单调递减
for head < tail && q[dq[tail–1]] <= q[i] {
tail—
}
dq[tail] = i
tail++

// 移除不属于当前窗口的下标
for head < tail && dq[head] <= i–window {
head++
}

// 当前已经形成一个完整的窗口
if i >= window {
l := i – window + 1
r := l + length – 1

// 原始检查耗时
total := sum[r] – sum[l–1]

// 最优免检收益
saved := q[dq[head]]

// 档位切换耗时
switching := S * int64(change[r]–change[l])

if total–saved+switching <= U {
return true
}
}
}

return false
}

func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()

fmt.Fscan(reader, &M, &W, &U, &S)

// 检查耗时
P := make([]int64, M+1)
G = make([]int, M+1)

// 前缀和
sum = make([]int64, M+1)

// 切换档位次数前缀和
change = make([]int, M+1)

for i := 1; i <= M; i++ {
fmt.Fscan(reader, &P[i])
sum[i] = sum[i–1] + P[i]
}

for i := 1; i <= M; i++ {
fmt.Fscan(reader, &G[i])
change[i] = change[i–1]

if i >= 2 && G[i] != G[i–1] {
change[i]++
}
}

// q[i] 表示从第 i 件开始，连续 W 件货物的检查耗时
n := M – W + 1
q = make([]int64, n+1)

for i := 1; i <= n; i++ {
q[i] = sum[i+W–1] – sum[i–1]
}

// 二分最长合法区间长度
left, right, ans := 1, M, 0

for left <= right {
mid := left + (right–left)/2

if check(mid) {
ans = mid
left = mid + 1
} else {
right = mid – 1
}
}

fmt.Fprintln(writer, ans)
}

javascript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const input = [];

rl.on('line', line => {
input.push(…line.trim().split(/\\s+/).filter(Boolean));
});

rl.on('close', () => {
let idx = 0;

const M = Number(input[idx++]);
const W = Number(input[idx++]);
const U = Number(input[idx++]);
const S = Number(input[idx++]);

// 检查耗时
const P = new Array(M + 1).fill(0);
const G = new Array(M + 1).fill(0);

// 前缀和
const sum = new Array(M + 1).fill(0);

// 切换档位次数前缀和
const change = new Array(M + 1).fill(0);

for (let i = 1; i <= M; i++) {
P[i] = Number(input[idx++]);
sum[i] = sum[i – 1] + P[i];
}

for (let i = 1; i <= M; i++) {
G[i] = Number(input[idx++]);
change[i] = change[i – 1];

if (i >= 2 && G[i] !== G[i – 1]) {
change[i]++;
}
}

// q[i] 表示从第 i 件开始，连续 W 件货物的检查耗时
const n = M – W + 1;
const q = new Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
q[i] = sum[i + W – 1] – sum[i – 1];
}

// 判断是否存在长度为 len 的合法区间
function check(len) {
// 整段都可以免检，只需要考虑档位切换耗时
if (len < W) {
for (let l = 1; l + len – 1 <= M; l++) {
const r = l + len – 1;
const cost = S * (change[r] – change[l]);

if (cost <= U) {
return true;
}
}

return false;
}

// 单调递减队列，维护 q 中长度为 len-W+1 的窗口最大值
const dq = new Array(n + 1);
let head = 0;
let tail = 0;
const window = len – W + 1;

for (let i = 1; i <= n; i++) {
// 保持队列中的 q 值单调递减
while (head < tail && q[dq[tail – 1]] <= q[i]) {
tail—;
}

dq[tail++] = i;

// 移除不属于当前窗口的下标
while (head < tail && dq[head] <= i – window) {
head++;
}

// 当前已经形成一个完整的窗口
if (i >= window) {
const l = i – window + 1;
const r = l + len – 1;

// 原始检查耗时
const total = sum[r] – sum[l – 1];

// 最优免检收益
const saved = q[dq[head]];

// 档位切换耗时
const switching = S * (change[r] – change[l]);

if (total – saved + switching <= U) {
return true;
}
}
}

return false;
}

// 二分最长合法区间长度
let left = 1;
let right = M;
let ans = 0;

while (left <= right) {
const mid = left + Math.floor((right – left) / 2);

if (check(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid – 1;
}
}

console.log(ans);
});