(C卷,100分)- 剩余银饰的重量（Java & JS & Python & C）

题目描述

有 N 块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。

每一回合，从中选出三块最重的银饰，然后一起熔掉。

假设银饰的重量分别为 x 、y和z，且 x ≤ y ≤ z。那么熔掉的可能结果如下：

• 如果 x == y == z，那么三块银饰都会被完全熔掉；
• 如果 x == y 且 y != z，会剩余重量为 z – y 的银块无法被熔掉；
• 如果 x != y 且 y == z，会剩余重量为 y – x 的银块无法被熔掉；
• 如果 x != y 且 y != z，会剩余重量为 z – y 与 y – x 差值 的银块无法被熔掉。

最后，

• 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
• 如果只剩下一块，返回该块的重量
• 如果没有剩下，就返回 0

输入描述

输入数据为两行：

• 第一行为银饰数组长度 n，1 ≤ n ≤ 40，
• 第二行为n块银饰的重量，重量的取值范围为[1，2000]，重量之间使用空格隔开

输出描述

如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；

如果只剩下一块，返回该块的重量；

如果没有剩下，就返回 0。

用例

题目解析

本题应该只是一道逻辑模拟题。

我们需要每次取出所有银饰中的最重的三个x,y,z，然后按照题目要求的规则：

• 如果 x == y == z，那么三块银饰都会被完全熔掉；
• 如果 x == y 且 y != z，会剩余重量为 z – y 的银块无法被熔掉；
• 如果 x != y 且 y == z，会剩余重量为 y – x 的银块无法被熔掉；
• 如果 x != y 且 y != z，会剩余重量为 z – y 与 y – x 差值 的银块无法被熔掉。

这里的规则其实可以总结为一个公式：

Math.abs((z – y) – (y – x))

带入上面x,y,z关系，即可推导出对应结果式。

这里需要注意的是，当 x != y 且 y != z，此时剩余重量为 z – y 与 y – x 差值 的银块，可能是0，即完全融掉的情况。

如果每次还有未熔完的银块，则重新加入到银饰中，然后再取出最重的三个银饰按照上面逻辑处理，直到所有银饰的数量不足三个，结束上面逻辑。

本题数量级不大，因此每次将未熔完的银块重新加入到银饰中后，可以对所有银饰进行重新排序。但是更优的做法是：

我们只对初始所有银饰进行一次升序，之后取出尾部三个最重的银饰，如果有未熔完的银块remain，那么就在剩余银饰（有序的）进行二分查找remain的有序插入位置，进行插入，这样可以提高效率。

关于二分查找有序插入位置可以看：

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 银饰数组长度
  const n = parseInt(await readline());

  // n块银饰的重量
  const weights = (await readline()).split(" ").map(Number);

  // 升序
  weights.sort((a, b) => a - b);

  while (weights.length >= 3) {
    // 尾删三个最大值
    const z = weights.pop();
    const y = weights.pop();
    const x = weights.pop();

    // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
    // 如果 x == y && y != z，那么下面公式结果：remain = z - y
    // 如果 x != y && y == z，那么下面公式结果：remain = y - x
    // 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
    const remain = Math.abs(z - y - (y - x));

    // 如果还有剩余银块
    if (remain != 0) {
      // 那么就二分查找其在剩余升序weights中的有序插入位置
      let idx = binarySearch(weights, remain);

      if (idx < 0) idx = -idx - 1;

      // 在有序插入位置插入
      weights.splice(idx, 0, remain);
    }
  }

  if (weights.length == 2) {
    // 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
    console.log(Math.max(weights[0], weights[1]));
  } else if (weights.length == 1) {
    // 如果只剩下一块，返回该块的重量
    console.log(weights[0]);
  } else {
    // 如果没有剩下，就返回 0
    console.log(0);
  }
})();

function binarySearch(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    const midVal = nums[mid];

    if (midVal > target) {
      high = mid - 1;
    } else if (midVal < target) {
      low = mid + 1;
    } else {
      return mid;
    }
  }

  return -low - 1;
}

Java算法源码

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

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

    // 银饰数组长度
    int n = sc.nextInt();

    // n块银饰的重量
    LinkedList<Integer> weights = new LinkedList<>();
    for (int i = 0; i < n; i++) {
      weights.add(sc.nextInt());
    }

    // 升序
    weights.sort((a, b) -> a - b);

    while (weights.size() >= 3) {
      // 尾删三个最大值
      int z = weights.removeLast();
      int y = weights.removeLast();
      int x = weights.removeLast();

      // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
      // 如果 x == y && y != z，那么下面公式结果：remain = z - y
      // 如果 x != y && y == z，那么下面公式结果：remain = y - x
      // 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
      int remain = Math.abs((z - y) - (y - x));

      // 如果还有剩余银块
      if (remain != 0) {
        // 那么就二分查找其在剩余升序weights中的有序插入位置
        int idx = Collections.binarySearch(weights, remain);

        if (idx < 0) {
          idx = -idx - 1;
        }

        // 在有序插入位置插入
        weights.add(idx, remain);
      }
    }

    if (weights.size() == 2) {
      // 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
      System.out.println(Math.max(weights.get(0), weights.get(1)));
    } else if (weights.size() == 1) {
      // 如果只剩下一块，返回该块的重量
      System.out.println(weights.get(0));
    } else {
      // 如果没有剩下，就返回 0
      System.out.println(0);
    }
  }
}

Python算法源码

# 输入获取
n = int(input())
weights = list(map(int, input().split()))


# 二分查找目标值位置，找不到则返回目标值在数组中有序插入位置
def binarySearch(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) >> 1
        midVal = nums[mid]

        if midVal > target:
            high = mid - 1
        elif midVal < target:
            low = mid + 1
        else:
            return mid

    return -low - 1


# 算法入口
def getResult():
    weights.sort()

    while len(weights) >= 3:
        # 尾删三个最大值
        z = weights.pop()
        y = weights.pop()
        x = weights.pop()

        # 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
        # 如果 x == y && y != z，那么下面公式结果：remain = z - y
        # 如果 x != y && y == z，那么下面公式结果：remain = y - x
        # 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
        remain = abs((z - y) - (y - x))

        # 如果还有剩余银块
        if remain != 0:
            # 那么就二分查找其在剩余升序weights中的有序插入位置
            idx = binarySearch(weights, remain)

            if idx < 0:
                idx = -idx - 1

            # 在有序插入位置插入
            weights.insert(idx, remain)

    if len(weights) == 0:
        # 如果没有剩下，就返回 0
        return 0
    else:
        # 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
        # 如果只剩下一块，返回该块的重量
        return max(weights)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

// 二分查找目标值位置，找不到则返回目标值在数组中有序插入位置
int binarySearch(const int *nums, int nums_size, int target) {
    int low = 0;
    int high = nums_size - 1;

    while (low <= high) {
        int mid = (low + high) >> 1;
        int midVal = nums[mid];

        if (midVal > target) {
            high = mid - 1;
        } else if (midVal < target) {
            low = mid + 1;
        } else {
            return mid;
        }
    }

    return -low - 1;
}

int main() {
    // 银饰数组长度
    int n;
    scanf("%d", &n);

    // n块银饰的重量
    int weights[n];
    int weights_size = 0;
    while (scanf("%d", &weights[weights_size++])) {
        if (getchar() != ' ') break;
    }

    // 升序
    qsort(weights, n, sizeof(int), cmp);

    while (weights_size >= 3) {
        // 尾删三个最大值
        int z = weights[weights_size - 1];
        int y = weights[weights_size - 2];
        int x = weights[weights_size - 3];

        weights_size -= 3;

        // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
        // 如果 x == y && y != z，那么下面公式结果：remain = z - y
        // 如果 x != y && y == z，那么下面公式结果：remain = y - x
        // 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
        int remain = abs((z - y) - (y - x));

        // 如果还有剩余银块
        if (remain != 0) {
            // 那么就二分查找其在剩余升序weights中的有序插入位置
            int idx = binarySearch(weights, weights_size, remain);

            if (idx < 0) {
                idx = -idx - 1;
            }

            // 在有序插入位置插入
            for (int i = weights_size - 1; i >= idx; i--) {
                weights[i + 1] = weights[i];
            }
            weights[idx] = remain;
            weights_size++;
        }
    }

    if (weights_size == 2) {
        // 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
        printf("%dn", MAX(weights[0], weights[1]));
    } else if (weights_size == 1) {
        // 如果只剩下一块，返回该块的重量
        printf("%dn", weights[0]);
    } else {
        // 如果没有剩下，就返回 0
        puts("0");
    }

    return 0;
}