class Solution {
public:
vector<int> supplyWagon(vector<int>& supplies) {
}
};
LCP 72. 补给马车
远征队即将开启未知的冒险之旅，不过在此之前，将对补给车队进行最后的检查。supplies[i] 表示编号为 i 的补给马车装载的物资数量。
考虑到车队过长容易被野兽偷袭，他们决定将车队的长度变为原来的一半（向下取整），计划为：
请返回车队长度符合要求后，物资的分布情况。
示例 1：
输入：
supplies = [7,3,6,1,8]输出：
[10,15]解释： 第 1 次合并，符合条件的两辆马车为 6,1，合并后的车队为 [7,3,7,8]； 第 2 次合并，符合条件的两辆马车为 (7,3) 和 (3,7)，取编号最小的 (7,3)，合并后的车队为 [10,7,8]； 第 3 次合并，符合条件的两辆马车为 7,8，合并后的车队为 [10,15]； 返回
[10,15]
示例 2：
输入：
supplies = [1,3,1,5]输出：
[5,5]
解释：
2 <= supplies.length <= 10001 <= supplies[i] <= 1000原站题解
python3 解法, 执行用时: 700 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-23 10:34:43
class Solution:
def supplyWagon(self, supplies: List[int]) -> List[int]:
k = len(supplies) // 2
while len(supplies) > k:
idx, min_sum = -1, inf
for i, (a, b) in enumerate(pairwise(supplies)):
if a + b < min_sum:
min_sum = a + b
idx = i
supplies[idx] += supplies[idx + 1]
supplies = supplies[: idx + 1] + supplies[idx + 2: ]
return supplies
python3 解法, 执行用时: 856 ms, 内存消耗: 15 MB, 提交时间: 2023-04-23 10:34:23
class Solution:
def supplyWagon(self, supplies: List[int]) -> List[int]:
length=len(supplies)//2 # 车队目标长度
while len(supplies)!=length: # 缩小长度逼近目标
list_sum = [] # 相邻两节马车之和组成的列表
for i in range(len(supplies) - 1):
list_sum.append(supplies[i] + supplies[i + 1])
merge=min(list_sum) # 本轮遍历中最小的相邻马车和
index_merge=list_sum.index(merge)
del supplies[index_merge+1]
supplies[index_merge]=merge # 整合马车
return supplies
javascript 解法, 执行用时: 96 ms, 内存消耗: 43.1 MB, 提交时间: 2023-04-23 10:33:39
/**
* @param {number[]} supplies
* @return {number[]}
*/
var supplyWagon = function (supplies) {
const len = supplies.length;
const target = Math.floor(len / 2);
const ans = supplies.slice();
while (ans.length > target) {
let min = Infinity;
let minIndex = -1;
for (let i = 0; i < ans.length - 1; i++) {
const sum = ans[i] + ans[i + 1];
if (sum < min) {
min = sum;
minIndex = i;
}
}
ans.splice(minIndex, 2, min);
}
return ans;
};
python3 解法, 执行用时: 84 ms, 内存消耗: 15.8 MB, 提交时间: 2023-04-23 10:33:10
class Solution:
def supplyWagon(self, s: List[int]) -> List[int]:
n = len(s)
fa = list(range(n))
low = list(range(n))
def find(x):
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
h = [(s[i] + s[i + 1], i, i + 1) for i in range(n - 1)]
heapify(h)
cnt = 0
while cnt < (n + 1) // 2:
x, i, j = heappop(h)
fi, fj = find(i), find(j)
if i == fi and j == fj and x == s[fi] + s[fj]:
cnt += 1
s[fj] += s[fi]
fa[fi] = fj
low[fj] = low[fi]
if low[fi] > 0:
fk = find(low[fi] - 1)
heappush(h, (s[fj] + s[fk], fk, fj))
if fj + 1 < n:
fk = find(fj + 1)
heappush(h, (s[fj] + s[fk], fj, fk))
ans = [s[i] for i in range(n) if find(i) == i]
return ans
java 解法, 执行用时: 13 ms, 内存消耗: 42.1 MB, 提交时间: 2023-04-23 10:32:45
class Solution {
public int[] supplyWagon(int[] supplies) {
int n = supplies.length;
for (int i = 0; i < (n + 1) / 2; i++) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < n - 1 - i; j++) {
int merge = supplies[j] + supplies[j + 1];
if (merge < min) {
min = merge;
minIndex = j;
}
}
supplies[minIndex] = min;
System.arraycopy(supplies, minIndex + 1 + 1, supplies, minIndex + 1, n - 1 - i - (minIndex + 1));
}
return Arrays.copyOf(supplies, n / 2);
}
}
cpp 解法, 执行用时: 168 ms, 内存消耗: 154.1 MB, 提交时间: 2023-04-23 10:32:28
class Solution {
public:
vector<int> supplyWagon(vector<int>& supplies) {
int n = supplies.size(), goal = n / 2;
while (supplies.size() > goal) {
// 找出物资之和最小，且编号最小的连续马车 pos 和 pos + 1
int pos = -1, best = 1e9;
for (int i = 0; i + 1 < supplies.size(); i++) {
int t = supplies[i] + supplies[i + 1];
if (t < best) pos = i, best = t;
}
// 计算新的队列，把结果存在 vec 里
vector<int> vec;
for (int i = 0; i < supplies.size(); i++) {
if (i == pos) {
// 这是我们要合并的马车
vec.push_back(best);
i++;
} else {
// 这个马车不需要合并
vec.push_back(supplies[i]);
}
}
// 把结果放回 supplies 里
supplies = vec;
}
return supplies;
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 42 MB, 提交时间: 2023-04-23 10:32:11
// 暴力模拟
class Solution {
public int[] supplyWagon(int[] supplies) {
int lengthA= supplies.length/2;//整理后的车队长度
int length= supplies.length;//原车队长度
int k=1,j=1,min=0;// min - k; i - j
while(length>lengthA) {//对车队长度修整并递减
int sum=1000000;//要求整合最小的，那我取一个最大的，来记录
boolean tag=true;
j=1;
for (int i = 0; i < supplies.length&&j< supplies.length; i++) {//遍历车队，i j 是相邻的两辆车
//1. 找车 i
while (supplies[i]==0) {//数值为 0，表示车子已经被合并，不存在了
i++;
if(i>= supplies.length){
tag=false;//结束标志
break;
}
}
if(!tag)//结束标志，结束 for 循环
break;
//2. 找车 j
j=i+1;
if(j>= supplies.length)
break;
while (supplies[j]==0) {
j++;
if(j>= supplies.length){
tag=false;
break;
}
}
if(!tag)//结束标志，结束 for 循环
break;
if(supplies[i]+supplies[j]<sum){//找到较小的相邻两车
min=i;
k=j;
sum=supplies[i]+supplies[j];
}
}
//找到当前车队最小的相邻两车，合并
supplies[min]=supplies[min]+supplies[k];
supplies[k]=0;
length--;
}
//返回新车队数组
int[] ans=new int[lengthA];
j=0;
for (int i = 0; i < lengthA&&j< supplies.length; i++,j++) {
while (supplies[j]==0)
j++;
ans[i]=supplies[j];
}
return ans;
}
}