【华为OD机试】分苹果

华为OD机试】分苹果"/>

【华为OD机试】分苹果

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

数据范畴： 1 <= 苹果数目 <= 20000 ，1 <= 每个苹果分量 <= 10000

输入

输入第一行是苹果数目:3

输入第二行是每个苹果分量:3 5 6

输出描写

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

示例一

输入

3
3 5 6

输出

11

思路：

机试第一题，上来就被唬住了，还以为是最头疼的背包问题，分析了一会发现A的计算方式实际上是二进制的异或运算（相同为0，不同为1），也就是说，A只用拿一个苹果就行了，因为再有一个苹果不管给A还是B，进行异或运算后结果都是相同的（满足A要求的前提下），那么问题就简单了，对苹果从小到大进行排序后，让A从小的开始拿，B拿剩余的，直到符合AB要求。

由于二进制的这些个转换操作不熟练，用了比较笨的方法强行转换，看个思路就好o(╯□╰)o

代码：

#include<bits/stdc++.h>
using namespace std;struct ac {int num;string two;
} a[1005];bool cmp(ac a, ac b) {return a.num < b.num;
}
//转换二进制
string fun(int a) {string s = "";for (int i = 13; i >= 0; i--) {int t = pow(2, i);if (a >= t) {a -= t;s += "1";} else {s += "0";}}return s;
}
//模仿异或运算
string gun(string a, string b) {string s = "";for (int i = 0; i < a.length(); i++) {if (a[i] == b[i])s += "0";elses += "1";}return s;
}int main() {int n, i, j, sum = 0;cin >> n;for (i = 0; i < n; i++) {cin >> a[i].num;a[i].two = fun(a[i].num);sum += a[i].num;//cout << fun(a[i].num) << endl;}sort(a, a + n, cmp);for (i = 0; i < n; i++) {string ti = a[i].two;string tj = "00000000000000";for (j = 0; j < n; j++) {if (j == i)continue;tj = gun(tj, a[j].two);}//cout << "ti tj:" << ti << " " << tj << endl;if (ti == tj) {cout << sum - a[i].num << endl;return 0;}}cout << "-1" << endl;return 0;
}