Tazi和kozi是两兄弟,妈妈给了他们一大袋糖,每块糖都有属于自己的重量。
现在他们想要将这些糖分成两堆。
分糖的任务当然落到了大哥Tazi的身上,然而kozi要求必须两个人获得的糖的总重量“相等”(根据kozi的逻辑),要不然就会哭的。
非常不幸的是,kozi还非常小,并且他只会先将两个数转成二进制再进行加法,而且总会忘记进位。
如当12(1100)加5(101)时:
1100
+ 0101
————
1001
于是kozi得到的计算结果是9(1001)。
此外还有一些例子:
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
现在Tazi非常贪婪,他想要尽可能使自己得到的糖的总重量最大,且不让kozi哭。
输入的第一行是一个整数 N( 2≤N≤15 ),表示有袋中多少块糖。
第二行包含N个用空格分开的整数 Weighti ( 1≤Weighti≤106 ),表示第i块糖的重量。
如果能让kozi不哭,输出Tazi所能获得的糖的总重量,否则输出“NO”。
输入
3
1 5 4
输出
9
这道题目要求将一组糖果分成两堆,使得按照kozi的加法方式(即二进制异或运算),两堆糖果的总重量相等。同时,塔子哥希望自己获得的糖果总重量尽可能大。
具体步骤 1.计算总体异或值和总重量:
遍历所有糖果,计算它们的总重量sum和总体异或值m。 同时,记录最小重量的糖果mn。
2.判断分组的可行性:
如果总体异或值m不为0: 无法将糖果分成两堆异或值相等的部分。 输出"NO",表示无法满足kozi的要求。
如果总体异或值m为0: 存在至少一种分组方式使得两堆糖果的异或值相等。 为了让塔子哥获得尽可能多的糖果,总重量最大化,可以采用贪心策略: 将重量最小的一块糖果分给kozi,这样塔子哥获得的糖果总重量为sum - mn。
3.输出结果:
根据上述判断,输出塔子哥的糖果总重量或"NO"
C++代码
#include<bits/stdc++.h>
using namespace std;
// 定义解决函数
void solve() {
int n; // 糖果的数量
int m = 0; // 总异或值初始化为0
long long sum = 0; // 总重量初始化为0
int mn = 1e9; // 最小重量初始化为一个较大的值
cin >> n; // 读取糖果的数量
// 遍历每一块糖果,读取其重量并更新总重量、总异或值和最小重量
for(int i = 0, x; i < n; ++i) {
cin >> x; // 读取第i块糖果的重量
sum += x; // 累加总重量
m ^= x; // 计算总异或值
mn = min(mn, x); // 更新最小重量
}
if(m == 0) { // 如果总异或值为0,表示可以分成两堆异或值相等
cout << sum - mn << endl; // 输出塔子哥可以获得的最大糖果总重量
} else { // 如果总异或值不为0,无法分成两堆异或值相等
cout << "NO" << endl; // 输出"NO"
}
}
signed main() {
solve(); // 调用解决函数
return 0; // 程序结束
}
python代码
def solve():
n = int(input()) # 读取糖果的数量
m = 0 # 初始化总异或值为0
total_sum = 0 # 初始化总重量为0
mn = int(1e9) # 初始化最小重量为一个较大的值
a = list(map(int, input().split())) # 读取所有糖果的重量并存储在列表a中
for x in a:
total_sum += x # 累加每块糖果的重量到总重量
m ^= x # 计算所有糖果重量的异或值
mn = min(mn, x) # 更新最小重量
if m == 0:
print(total_sum - mn) # 如果总异或值为0,输出塔子哥可以获得的最大糖果总重量
else:
print("NO") # 如果总异或值不为0,输出"NO",表示无法分组
if __name__ == "__main__":
solve()
Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
solve(); // 调用解决函数
}
static void solve() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 读取糖果的数量
int m = 0; // 初始化总异或值为0
long sum = 0; // 初始化总重量为0
int mn = 1000000000; // 初始化最小重量为一个较大的值
// 遍历每一块糖果,读取其重量并更新总重量、总异或值和最小重量
for (int i = 0; i < n; i++) {
int x = sc.nextInt(); // 读取第i块糖果的重量
sum += x; // 累加总重量
m ^= x; // 计算总异或值
mn = Math.min(mn, x); // 更新最小重量
}
if (m == 0) { // 如果总异或值为0,表示可以分成两堆异或值相等
System.out.println(sum - mn); // 输出塔子哥可以获得的最大糖果总重量
} else { // 如果总异或值不为0,无法分成两堆异或值相等
System.out.println("NO"); // 输出"NO"
}
sc.close(); // 关闭扫描器
}
}
本题属于以下题库,请选择所需题库进行购买