云计算百科
云计算领域专业知识百科平台

BISHI40数组取精

在这里插入图片描述

求解思路

1.先分别计算序列A和B的总和sumA 和sumB

2.将所有元素按照ai+bia_i +b_iai+bi从大到小排序

3.依次选取排序后的元素,累加子集的A和、B和,直到同时满足超过总和的一半

4.输出选取的元素的原始索引

求解代码

static class Element {
int a; // 对应数组A的元素值
int b; // 对应数组B的元素值
int index;// 该元素在原数组中的索引(从1开始)

// 构造方法:初始化a、b、index
Element(int a, int b, int index) {
this.a = a;
this.b = b;
this.index = index;
}
}

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());

String[] strA = br.readLine().split(" ");
String[] strB = br.readLine().split(" ");

PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

List<Element> elements = new ArrayList<>();

long sumA = 0, sumB = 0;

for (int i = 0; i < n; i++) {
int a = Integer.parseInt(strA[i]); // 把strA的字符串转成整数
int b = Integer.parseInt(strB[i]); // 把strB的字符串转成整数
elements.add(new Element(a, b, i + 1)); // 封装成Element,索引从1开始
sumA += a; // 累加A的总和
sumB += b; // 累加B的总和
}

Collections.sort(elements, (e1, e2) -> {
long s1 = (long) e1.a + e1.b;
long s2 = (long) e2.a + e2.b;

return Long.compare(s2, s1);// 按a+b从大到小排序
});

List<Integer> res = new ArrayList<>();
long currentA = 0, currentB = 0;

for (Element e : elements) {
res.add(e.index); // 把当前元素的索引加入结果
currentA += e.a; // 累加子集的A和
currentB += e.b; // 累加子集的B和
// 检查是否满足条件:子集和超过总和的一半
if (currentA > sumA / 2 && currentB > sumB / 2) {
break; // 满足条件则停止选取
}
}
out.println(res.size());

for (int i = 0; i < res.size(); i++) {
out.print(res.get(i)+(i == res.size() 1 ? "" : " "));
}

out.flush();
out.close();
br.close();
}

赞(0)
未经允许不得转载:网硕互联帮助中心 » BISHI40数组取精
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!