思路：贪心+排序

把数组按照特殊值的大小降序排列，然后一边模拟，一边判断当前元素加入进来是否能保证特殊元素总和>=总的元素和的一半，如果可以，就加入，不可以，直接退出循环(因为后面的就更不可能满足条件)

代码

C++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e6 + 10;
typedef pair<int, int> PII;
PII items[N];
#define a first
#define b second

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
       cin >> items[i].a;
    }
    for(int i = 0; i < n; i++) {
       cin >> items[i].b;
    }

    sort(items, items + n);

    int special = 0, normal = 0;
    for(int i = n - 1; i >= 0; i--) {
        if (special + items[i].a >= normal + items[i].b) {
            special += items[i].a;
            normal += items[i].b;
        } else break;
    }

    cout << special << endl;
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;


public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = input.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = input.nextInt();
        }
        int res = getMaxSpecialElements(a, b);
        System.out.println(res);
    }
    public static int getMaxSpecialElements(int[] specialElements, int[] normalElements) {
        int n = specialElements.length;
        int[][] props = new int[n][2]; // 存储道具的特殊元素数量和普通元素数量

        // 初始化props数组
        for (int i = 0; i < n; i++) {
            props[i][0] = specialElements[i];
            props[i][1] = normalElements[i];
        }
        // 对道具按特殊元素数量从高到低排序
        Arrays.sort(props, (a, b) -> Integer.compare(b[0], a[0]));

        int selectedSpecial = 0; // 已选择的特殊元素总数
        int selectedNormal = 0; // 已选择的普通元素总数

        // 从数量最多的特殊元素开始选择道具
        for (int i = 0; i < n; i++) {
            // 如果特殊元素的总数已经超过或等于普通元素的总数，停止选择
            if (selectedSpecial + props[i][0] < selectedNormal + props[i][1]) {
                break;
            }
            selectedSpecial += props[i][0];
            selectedNormal += props[i][1];
        }
        // 计算最大特殊元素数量
        return selectedSpecial;
    }
}

Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(zip(a, b))
c = sorted(c, key= lambda x: (- x[0], x[1]))
res = 0
cnt_a = 0
cnt_b = 0
for i in range(n):
    cnt_a += c[i][0]
    cnt_b += c[i][1]
    if cnt_a >= cnt_b:
        res = cnt_a
    else:
        break
print(res)

题目描述

小红喜欢魔术，现在有 $n$ 个魔术道具，这些道具由不同的物品组成。其中第$i$个道具包含$a_i$个特殊元素，包含$b_i$个普通元素。

小红想最大化他的魔术表演，但他的魔术需要特殊元素所占的比例不能低于一半。

小红需要选择一些道具，将它们的特殊元素混合在一起，问小红最多可以得到多少特殊元素用作魔术表演？

输入描述

一行一个整数$n$，表示道具的数量。

接下来一行，$n$个整数$a_1,a_2,...，a_n$，表示第i个道具包含$a_i$个特殊元素。

接下来一行，$n$个整数$b_1,b_2,....,b_n$，表示第i个道具包含$b_i$个普通元素。

$1 \leq n \leq 10^5$

$0 \leq a_i, b_i \leq 100$

$a_i + b_i = 100$

输出描述

一行一个整数，表示小红最多可以得到的特殊元素数量。

样例

输入

3
50 60 30
50 40 70

输出

110

说明

选择第一和第二个道具，可以得到110个特殊元素。