每日一题&&学习笔记

问题描述

为了修复黄金律法，MaverickFW 收集了传说中的武器和传说中的魔法。MaverickFW 的武器槽和魔法槽都有 N 个，但是在战斗中同时切换武器和魔法太痛苦了。为了简化操作，MaverickFW 决定重新排列 N 个武器或者魔法使得冲突最小。我们设定每个武器都有一个属性值 w，每个魔法有一个属性值 m，冲突定义为 ∑i=1n(w×m)。

输入格式

输入第 1 行包含一个正整数 T，表示测试数据的组数。

对于每一组数据，第 1 行包含一个正整数 n，表示武器槽和魔法槽的数量。

第 2 行包含 n 个整数 wi​，表示所有武器属性值。

第 3 行包含 n 个整数 mi​，表示所有魔法属性值。

输出格式

对于每组测试数据，输出一行一个整数，表示重新排列后最小的冲突值。

输入样例

1

5

1 2 3 4 5

5 4 3 2 1

输出样例

35

#include <iostream>  
#include <algorithm>  
using namespace std;  
  
const int N = 1e5; // 数组的最大可能长度  
  
int main() {  
    int T; // 测试用例的数量  
    cin >> T;  
    for (int k = 0; k < T; k++) {  
        int n; // 当前测试用例中数组的长度  
        cin >> n;  
        int a[N], b[N]; // 定义两个数组  
        for (int i = 0; i < n; i++) {  
            cin >> a[i];  
        }  
        for (int i = 0; i < n; i++) {  
            cin >> b[i];  
        }  
        sort(a, a + n); // 对数组a进行升序排序  
        sort(b, b + n); // 对数组b也进行升序排序，但我们将在后面“反向”使用它  
  
        long long sum = 0; // 用于存储乘积和的变量  
        for (int j = 0; j < n; j++) {  
            // 数组a的第j个元素与数组b的第j个元素相乘（但由于b是升序的，我们实际上想要的是b的降序版本中的第j个元素，  
            // 所以这里直接取b[n-j-1]就实现了“虚拟”的降序处理）  
            // 但为了保持代码的直观性，并且因为我们已经知道要对b进行这样的处理，所以这里还是写b[j]，  
            // 但在解释时指出我们实际上是如何“反向”使用b的。  
            // 注意：为了真正最小化乘积和，我们应该直接写b[n-j-1]，如下一行所示。  
            sum += a[j] * b[n - j - 1]; // 正确的做法，使用b的“降序”版本中的元素  
        }  
  
        cout << sum << endl; // 输出最小乘积和  
    }  
    return 0;  
}

这道题的做法是用贪心去找每一次相乘得到的最小值，使用让一个数组的最大值和另一个数组的最小值相乘，这样相对而言每次都能得到一个最小的值，最后的和一定就是最小的

原文地址：https://blog.csdn.net/m0_73096516/article/details/142903191

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！