c++ - 在两个 vector 之间交换值，使两个 vector 的 max_elements 之和最小

Question

这是来自 Codechef 的问题，但请耐心等待。 https://www.codechef.com/ZCOPRAC/problems/ZCO16001

该竞赛是为在印度举行的 Zonal Computing Olympiad 做准备，因此它不是一个我可以从中获得一些东西的竞争性竞赛。只需要一点帮助来查看我的代码有什么问题，因为我觉得我忽略了一些大而愚蠢的事情。 :P

所以基本上这个问题总结起来就是这样。

Lets say that there are two vectors or arrays. You need to swap elements between them such that the sum of their maximum elements is minimum. However you can swap at most K times. Then output the value of this sum.

我的方法很简单。从 Vector1 (V1) 中取出最大的数字并将其与 V2 中的最小数字交换。添加每个的最高值。做同样的事情，但这次将 V2 中的最高数字与 V1 中的最低数字交换。添加每个的最高值。更好的交换将是总和最低的交换，并从那里继续 K 次。

例如:

V1 = 5 6 7 9

V2 = 9 10 5 4

在这种情况下，如果 K = 1我首先将 V1 的 9 与 V2 的 4 交换。这给出:

V1 = 5 6 7 4

V2 = 9 10 5 9

与之前的 19 相比，最高数字的总和为 17。我可以做的第二个交换是 V2 的 10 和 V1 的 5 给出:

V1 = 10 6 7 4

V2 = 9 5 5 9

这给出的总和为 19，所以第一次交换更好，输出应该是 17。

这是我的解决方案:

#include <iostream>
#include <vector>
#include <algorithm>
#define print(vec) for (int i  = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl;
using namespace std;

vector <long long int> s1, s2;

inline long long int calc(vector <long long int> v1, vector<long long int> v2) {
    return *max_element(v1.begin(), v1.end()) + *max_element(v2.begin(), v2.end());
}
int main(){


    long long int n, k;
    cin >> n >> k;
    long long int x;
    for (unsigned int i = 0; i < n; i++) {
        cin >> x;
        s1.push_back(x);
    }
    for (unsigned int i = 0; i < n; i++) {
        cin >> x;
        s2.push_back(x);
    }
    while (k--) {

        vector <long long int> b1(s1);
        vector <long long int> b2(s2);
        long long int skewb = calc(b1,b2);

        vector <long long int> v1(s1);
        vector <long long int> v2(s2);

        auto mn1 = minmax_element(v1.begin(), v1.end());
        auto mn2 = minmax_element(v2.begin(), v2.end());

        iter_swap(mn1.second, mn2.first);

        b1 = vector <long long int> (v1);
        b2 = vector <long long int> (v2);
        skewb = calc(v1,v2);

        v1 = vector <long long int> (s1);
        v2 = vector <long long int> (s2);
        mn1 = minmax_element(v1.begin(), v1.end());
        mn2 = minmax_element(v2.begin(), v2.end());

        iter_swap(mn2.second, mn1.first);
        if (calc(v1,v2) <= skewb) {
            b1 = vector <long long int> (v1);
            b2 = vector <long long int> (v2);
        }

        if (b1 == s1 && b2 == s2) cout << "LOL" << endl;
        s1 = vector <long long int> (b1);
        s2 = vector <long long int> (b2);
    }



    cout << calc(s1, s2) << endl;
}

请注意，这会进行所有交换，即 K。因此，即使当前安排是最好的，它仍会交换一些值。早些时候，当当前的安排是最好的时候，我正在打破。这样做的原因是因为除了两个之外，我所有的测试用例都是正确的!猜猜更烦人的是，每个任务都有一个! :(所以我意识到必须完成所有 K 开关。然而，即使是现在我也有 2 个测试用例出错，一定有一些我忽略的地方。

知道它是什么吗？解决方案链接:https://www.codechef.com/viewsolution/11574501

顺便说一下，任务 1 的 K = 1。

Answer 1

您的代码的问题是您在交换之间更改数组，因此有可能在数组之间来回交换一个项目。我的意思是，在第一次交换中，您将元素 x 从 array1 放置到 array2 中，而在下一次交换中，您可能会再次将其交换回去。

你还做了很多 vector 复制，这使得代码效率低下。即使您的代码逻辑正确，您的代码也不会超过时间限制，因为您的方法是 O(n²)。

---

首先请注意，最佳答案是当一个数组中的所有元素都大于另一个数组中的所有元素时。

• 对两个数组进行排序
• 对于 x 从 0 到 k
  • 假设将第一个数组的 x 个最小元素与第二个数组的 x 个最大元素交换。
  • result = min(result, max(result, max(第一个数组) + max(第二个数组))
  • 假设将第一个数组的 x 个最大元素与第二个数组的 x 个最小元素交换。
  • result = min(result, max(result, max(第一个数组) + max(第二个数组))
• result 将包含最终答案

由于两个数组都已排序，您可以在假设交换后通过一次比较找到数组的最大元素。

V1 = 5 6 7 9 -> 5 6 7 9
V2 = 9 10 5 4 -> 4 5 9 10

x = 0   no swaps: result = V1[size-1] + V2[size-1]
x = 1 
        result = max(V1[size-1], V2[size-1]) + max(V1[0], V2[size-2])
        result = max(V1[size-2], V2[0]) + max(V1[size-1],V2[size-1])
x = 2 
        result = max(V1[size-1], V2[size-1]) + max(V1[1], V2[size-3])
        result = max(V1[size-3], V2[1]) + max(V1[size-1],V2[size-1])
...

这是公认的实现:

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;


int main()
{
    int n,k;
    cin>>n>>k;

    vector<int> v[2];
    for ( int i=0;i < 2;++i ){
        for ( int j=0;j<n;++j ){
            int temp; cin>> temp;
            v[i].push_back(temp);
        }
    }

    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());

    int result = v[0].back() + v[1].back();

    for ( int i=1; i<=k; ++i ){
        int t = max(v[0][n-1],v[1][n-1]) + max(v[0][i-1],v[1][n-1-i]);
        result = min(result,t);
        t = max(v[0][n-1-i],v[1][i-1]) + max(v[0][n-1],v[1][n-1]);
        result = min(result,t);
    }

    cout << result << endl;
}