1. Description
给定一个包含 n 个正整数的数组 nums。
可以删除数组中的至多一个元素，也可以不删除任何元素。删除后，其余元素的相对顺序保持不变。
随后，将剩余数组分割成两个非空连续部分。设左半部分元素之和为 leftSum，右半部分元素之和为 rightSum。
请返回所有合法操作中最小的 leftSum 与 rightSum 的差值。
2. Solution
Time complexity: O(nlogn)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| int main() {
int T;
cin >> T;
while (T-- > 0) {
int n;
cin >> n;
vector<int64_t> weights(n);
multiset<int64_t> left_weights, right_weights;
for (int i = 0; i < n; ++i) {
cin >> weights[i];
right_weights.insert(weights[i]);
}
int64_t min_diff = numeric_limits<int64_t>::max();
int64_t left_sum = 0;
int64_t right_sum = accumulate(weights.begin(), weights.end(), 0LL);
for (int i = 0; i < n - 1; ++i) {
left_sum += weights[i];
right_sum -= weights[i];
left_weights.insert(weights[i]);
auto iter = right_weights.find(weights[i]);
right_weights.erase(iter);
if (left_sum > right_sum) {
int64_t diff = left_sum - right_sum;
min_diff = min(min_diff, diff);
if (left_weights.size() > 1) {
auto iter = left_weights.lower_bound(diff);
if (iter != left_weights.end()) {
min_diff = min(min_diff, *iter - diff);
}
auto prev_iter = iter;
if (prev_iter != left_weights.begin()) {
--prev_iter;
min_diff = min(min_diff, diff - *prev_iter);
}
}
} else if (left_sum == right_sum) {
min_diff = 0;
break;
} else {
int64_t diff = right_sum - left_sum;
min_diff = min(min_diff, diff);
if (right_weights.size() > 1) {
auto iter = right_weights.lower_bound(diff);
if (iter != right_weights.end()) {
min_diff = min(min_diff, *iter - diff);
}
auto prev_iter = iter;
if (prev_iter != right_weights.begin()) {
--prev_iter;
min_diff = min(min_diff, diff - *prev_iter);
}
}
}
}
cout << min_diff << endl;
}
return 0;
}
|