C++中如何基于两个数组排序并保留元素原始索引？

核心逻辑很直接：把两个数组中对应位置的元素绑定成单个单元（对象/结构体/元组），统一按a/b比值排序，之后贪心选取时直接遍历排序后的列表即可，每次取最优元素的操作复杂度降到O(1)。

不同语言的实现示例 #

Python

# 示例数组：a代表价值，b代表重量
a = [10, 20, 30]
b = [2, 5, 6]

# 打包对应元素为元组列表
elements = list(zip(a, b))
# 按a/b比值降序排序（假设比值越大越优）
elements.sort(key=lambda x: x[0]/x[1], reverse=True)

# 贪心选取过程（以总重量限制为例）
remaining_weight = 10
total_value = 0
for val, weight in elements:
    if remaining_weight >= weight:
        total_value += val
        remaining_weight -= weight
    else:
        # 允许拆分元素时取部分价值
        total_value += val * (remaining_weight / weight)
        remaining_weight = 0
        break

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

// 定义元素类绑定a和b
class Element {
    int a;
    int b;
    public Element(int a, int b) {
        this.a = a;
        this.b = b;
    }
}

public class GreedyDemo {
    public static void main(String[] args) {
        int[] a = {10, 20, 30};
        int[] b = {2, 5, 6};
        ArrayList<Element> elements = new ArrayList<>();

        // 打包元素
        for (int i = 0; i < a.length; i++) {
            elements.add(new Element(a[i], b[i]));
        }

        // 按a/b降序排序
        Collections.sort(elements, (e1, e2) -> {
            double ratio1 = (double) e1.a / e1.b;
            double ratio2 = (double) e2.a / e2.b;
            return Double.compare(ratio2, ratio1);
        });

        // 贪心选取
        int remainingWeight = 10;
        double totalValue = 0;
        for (Element e : elements) {
            if (remainingWeight >= e.b) {
                totalValue += e.a;
                remainingWeight -= e.b;
            } else {
                totalValue += e.a * ((double) remainingWeight / e.b);
                remainingWeight = 0;
                break;
            }
        }
    }
}

C++

#include <vector>
#include <algorithm>

// 结构体绑定a和b
struct Element {
    int a;
    int b;
};

// 排序比较器：用交叉相乘避免浮点精度误差（a、b为正整数时适用）
bool compare(const Element& e1, const Element& e2) {
    return (long long)e1.a * e2.b > (long long)e2.a * e1.b;
}

int main() {
    int a[] = {10, 20, 30};
    int b[] = {2, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    std::vector<Element> elements;

    // 打包元素
    for (int i = 0; i < n; i++) {
        elements.push_back({a[i], b[i]});
    }

    // 按比值降序排序
    std::sort(elements.begin(), elements.end(), compare);

    // 贪心选取
    int remainingWeight = 10;
    double totalValue = 0;
    for (const auto& e : elements) {
        if (remainingWeight >= e.b) {
            totalValue += e.a;
            remainingWeight -= e.b;
        } else {
            totalValue += e.a * ((double)remainingWeight / e.b);
            remainingWeight = 0;
            break;
        }
    }
    return 0;
}

注意事项 #

• 如果b可能为0，需提前过滤或做特殊判断，避免除以零错误。
• 当a、b均为正整数时，用交叉相乘代替浮点除法比较比值，能避免精度损失（如C++示例中的做法）。
• 整体时间复杂度为O(n log n)（排序）+ O(n)（选取），比原方案的O(n²)高效得多，适合大数据量场景。

内容的提问来源于stack exchange，提问作者areksuu