问题
有一批货，体积大小随机，有一批箱子，体积固定为3，不考虑货物的体积，求给定货物最多能装满几个箱子。
说明：体积为6的货物可以用2个箱子装完，体积为7的箱子不能被箱子装下
思路
当货物的体积为3的整数倍时，货物可以刚好装满箱子
当货物总体积除以3余1时，说明至少存在一个体积除3余1的货物，剔除其中最小的一个即可。
当货物体积除以3余2时，说明可能存在偶数个除3与1的货物或奇数个除3余2的货物。剔除2个最小除3余1的货物
或者剔除最小的一个除3余2的货物即可。
伪代码：
int[] mode1 = int[2];
int mode2;
int sumVolum;
if(sumVolum % 3 == 0) {
return sumVolum / 3;
}
if(sumVolum % 1 == 0) {
return (sumVolum - mode1[0])/3;
}
if(mode1[1] == 0 || mode1[1] == 0) {
return (sumVolum - mode2)/3;
}
int tmpSum = mode1[1] + mode1[1];
if(tmpSum > mode2) {
return (sumVolum - mode2)/3;
}
return (sumVolum - tmpSum)/3;
|
这里有个技巧，就是如何一次循环得到倒数1，2的两个最小的货物。思路是：
如果mode1[0] == 0，就先填充mode1[0]。
如果校验货物的体积比mode1[0]小，替换mode1[0]为校验货物，并将mode1[0]之间的值放置到mode1[1]
如果校验货物的提交比mode1[0]大，但是mode1[1]==0。将检验货物放置到mode1[1]。
如果校验货物的体积比mode1[0]大，但比mode1[1]小，那么将检验货物放置到mode1[1]。
代码实现
public int solution(int[] arr) {
int[] mode1 = new int[2];
int mode2 = 0;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] % 3 == 1) {
if (mode1[0] == 0) {
mode1[0] = arr[i];
sum += arr[i];
continue;
}
if (mode1[0] > arr[i]) {
mode1[1] = mode1[0];
mode1[0] = arr[i];
sum += arr[i];
continue;
}
if (mode1[1] > arr[i]) {
mode1[1] = arr[i];
sum += arr[i];
continue;
}
if (mode1[1] == 0) {
mode1[1] = arr[i];
sum += arr[i];
continue;
}
}
if (arr[i] % 3 == 2) {
if (mode2 == 0) {
mode2 = arr[i];
sum += arr[i];
continue;
}
if (mode2 > arr[i]) {
mode2 = arr[i];
}
}
sum += arr[i];
}
int mode = sum % 3;
if(mode == 0) {
return sum / 3;
}
if (mode == 1) {
return (sum - mode1[0]) / 3;
}
if(mode1[0] == 0 || mode1[1] == 0) {
return (sum - mode2) / 3;
}
int nums = mode1[0] + mode1[1];
if (nums > mode2) {
return (sum - mode2) / 3;
}
return (sum - nums) / 3;
}
|
校验代码
int[] arr = {3, 6, 5, 1, 8};
int ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 6, MelonStatusCodeEnums.SYSTEM_ERROR);
arr = new int[]{3, 6, 5, 1, 5, 1, 8};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 9, MelonStatusCodeEnums.SYSTEM_ERROR);
arr = new int[]{5};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 0, MelonStatusCodeEnums.SYSTEM_ERROR);
arr = new int[]{5, 1};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 2, MelonStatusCodeEnums.SYSTEM_ERROR);
arr = new int[]{5, 1};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 2, MelonStatusCodeEnums.SYSTEM_ERROR);
|