• OD华为机试 19


    分苹果

    描述

    A、B两个人把苹果分为两堆,A希望按照他的计算规则等分苹果,他的计算规则是按照二进制加法计算,并且不计算进位 12+5=9(1100 + 0101 = 9),B的计算规则是十进制加法,包括正常进位,B希望在满足A的情况下获取苹果重量最多。

    输入苹果的数量和每个苹果重量,输出满足A的情况下B获取的苹果总重量。

    如果无法满足A的要求,输出-1。

    输入描述:
    输入第一行是苹果数量:3
    输入第二行是每个苹果重量:3 5 6

    输出描述:
    输出第一行是B获取的苹果总重量:11

    测试用例
    示例1:
    输入

    3
    3 5 6
    
    • 1
    • 2

    输出

    11
    
    • 1

    示例2:
    输入

    8
    7258 6579 2602 6716 3050 3564 5396 1773
    
    • 1
    • 2

    输出

    35165
    
    • 1

    法一

    import java.util.*;
    
    public class Main {
        public static final int INVALID_NUM = -1;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                int num = Integer.parseInt(sc.nextLine());
                List<Integer> list = new ArrayList<>();
                for (int i = 0 ; i < num ; i++) {
                    list.add(sc.nextInt());
                }
                //一个计数a,a要求相加之后对等,因为采用二进制而不进位,所以等同于异或
                int aWeight = 0;
                int bWeight = 0;
                int min = Integer.MAX_VALUE;
                for (int i : list) {
                    aWeight ^= i;
                    bWeight += i;
                    min = Math.min(i, min);
                }
    
                if (aWeight == 0) {
                    System.out.println(bWeight - min);
                } else {
                    System.out.println(INVALID_NUM);
                }
            }
        }
    }
    
    • 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
    算法实现

    首先,如果能满足 A,那么所有苹果全部 “异或”操作后,必然是0 。
    这是有一个比较巧妙的地方在于:

    二进制加法不进位情况,恰恰就是异或的运行规则。

    如例一所示:5(101) + 6 (110) = 3(011),
    那么等式左边转为二进制后,一定是要和右边一模一样,每一位都一样,这样才能保证等分,因此我们可以先用异或,算出等式左边,然后此时如果再用一次异或来与等式右边比较,异或运行规则是,这一位相同,则结果是0,这一位不同,则结果是1。
    其次,要想 B 最多,只需要将这堆苹果中,最小的一个给A即可。因为所有苹果异或的结果是0,所以任意拿出1个,分成另一堆, 那么剩下的就是B 想要的重量

  • 相关阅读:
    Kotlin协程:生命周期原理
    DNS大全(114DNS 、阿里DNS、百度DNS 、360 DNS、Google DNS)
    【物理应用】基于摩尔库仑准则实现应变软化岩体的围岩-支护相互作用附matlab代码
    基于springboot的医院体检预约管理系统
    人脸核身基础版 SDK 接入 > 合作方后台上送身份信息
    成功的性能测试方法的 3 个阶段
    LeetCode刷题---LRU缓存
    kubernetesr进阶--污点和容忍之基于污点的驱逐
    Spark SQL中的正则表达式应用
    ovs实现的几种openflow扩展消息
  • 原文地址:https://blog.csdn.net/starry_night_summer/article/details/127899285