【华为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
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";
		else
			s += "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;
}