牛牛的数组匹配
[题目链接](https://www.nowcoder.com/practice/3d3406f4a7eb4346b025cc592be5b875)
思路
给定数组 (长度
)和数组
(长度
),找出
中连续子数组之和与
最接近的那一段。若有多段同样接近,取起始位置最靠左的。
做法:前缀和 + 二分查找
设 ,
(
)。
子数组 的和为
。我们需要找使
最小的
对,即对每个起点
,在
中找最接近
的值。
由于题目保证数组元素均为正整数,前缀和严格递增,因此可以用二分查找在 时间内定位最接近的位置。对每个
,检查二分定位点及其左邻两个候选即可。
遍历所有起点 ,维护全局最小差值和对应的最左起始位置。
复杂度分析
- 时间复杂度:
,对每个起点做一次二分查找。
- 空间复杂度:
,存储前缀和数组。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
scanf("%d%d", &n, &m);
long long sumA = 0;
for(int i = 0; i < n; i++){
long long x; scanf("%lld", &x);
sumA += x;
}
vector<long long> b(m);
for(int i = 0; i < m; i++) scanf("%lld", &b[i]);
vector<long long> pre(m+1, 0);
for(int i = 0; i < m; i++) pre[i+1] = pre[i] + b[i];
long long bestDiff = LLONG_MAX;
int bestL = 0, bestR = 0;
for(int i = 0; i < m; i++){
long long target = sumA + pre[i];
int lo = i+1, hi = m;
int left = lo, right = hi;
while(left <= right){
int mid = (left + right) / 2;
if(pre[mid] >= target) right = mid - 1;
else left = mid + 1;
}
for(int c = max(lo, left-1); c <= min(hi, left); c++){
long long diff = abs(pre[c] - target);
if(diff < bestDiff || (diff == bestDiff && i < bestL)){
bestDiff = diff;
bestL = i;
bestR = c - 1;
}
}
}
for(int i = bestL; i <= bestR; i++){
if(i > bestL) printf(" ");
printf("%lld", b[i]);
}
printf("\n");
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long sumA = 0;
for (int i = 0; i < n; i++) sumA += sc.nextLong();
long[] b = new long[m];
for (int i = 0; i < m; i++) b[i] = sc.nextLong();
long[] pre = new long[m + 1];
for (int i = 0; i < m; i++) pre[i + 1] = pre[i] + b[i];
long bestDiff = Long.MAX_VALUE;
int bestL = 0, bestR = 0;
for (int i = 0; i < m; i++) {
long target = sumA + pre[i];
int lo = i + 1, hi = m;
int left = lo, right = hi;
while (left <= right) {
int mid = (left + right) / 2;
if (pre[mid] >= target) right = mid - 1;
else left = mid + 1;
}
for (int c = Math.max(lo, left - 1); c <= Math.min(hi, left); c++) {
long diff = Math.abs(pre[c] - target);
if (diff < bestDiff || (diff == bestDiff && i < bestL)) {
bestDiff = diff;
bestL = i;
bestR = c - 1;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = bestL; i <= bestR; i++) {
if (i > bestL) sb.append(' ');
sb.append(b[i]);
}
System.out.println(sb.toString());
}
}
import bisect, sys
input = sys.stdin.readline
def main():
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sumA = sum(a)
pre = [0] * (m + 1)
for i in range(m):
pre[i + 1] = pre[i] + b[i]
best_diff = float('inf')
best_l = 0
best_r = 0
for i in range(m):
target = sumA + pre[i]
lo = i + 1
pos = bisect.bisect_left(pre, target, lo, m + 1)
for c in range(max(lo, pos - 1), min(m, pos) + 1):
diff = abs(pre[c] - target)
if diff < best_diff or (diff == best_diff and i < best_l):
best_diff = diff
best_l = i
best_r = c - 1
print(' '.join(map(str, b[best_l:best_r + 1])))
main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
const [n, m] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
const b = lines[2].split(' ').map(Number);
let sumA = 0;
for (let i = 0; i < n; i++) sumA += a[i];
const pre = new Array(m + 1).fill(0);
for (let i = 0; i < m; i++) pre[i + 1] = pre[i] + b[i];
let bestDiff = Infinity;
let bestL = 0, bestR = 0;
for (let i = 0; i < m; i++) {
const target = sumA + pre[i];
let lo = i + 1, hi = m;
let left = lo, right = hi;
while (left <= right) {
const mid = (left + right) >> 1;
if (pre[mid] >= target) right = mid - 1;
else left = mid + 1;
}
for (let c = Math.max(lo, left - 1); c <= Math.min(hi, left); c++) {
const diff = Math.abs(pre[c] - target);
if (diff < bestDiff || (diff === bestDiff && i < bestL)) {
bestDiff = diff;
bestL = i;
bestR = c - 1;
}
}
}
const res = [];
for (let i = bestL; i <= bestR; i++) res.push(b[i]);
console.log(res.join(' '));
});

京公网安备 11010502036488号