交换两个向量之间的值,使两个向量的max_elements之和最小

Question

这是Codechef提出的问题,但请耐心等待. https://www.codechef.com/ZCOPRAC/problems/ZCO16001

这场比赛是为了准备在印度举办的Zonal计算奥林匹克运动会,所以它不是一场竞争性的比赛,我可以从中获得这样的比赛.只需要一些帮助就可以看出我的代码有什么问题,因为我有一种感觉,我忽略了一些大而愚蠢的东西.:P

所以基本上这个问题总结为这个.

可以说有两个向量或数组.您需要在它们之间交换元素,以使它们的最大元素之和最小.但是,您最多可以交换K次.然后输出此总和的值.

我的方法很简单.取Vector1(V1)中的最大数字,并将其与V2中的最低值交换.添加每个的最高值.这样做,但这次交换V2中的最高数字与V1中的最低数字.添加每个的最高值.更好的交换将是具有最低总和的那个并且从那里继续K次.

例如:

V1 = 5 6 7 9

V2 = 9 10 5 4

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

V1 = 5 6 7 4

V2 = 9 10 5 9

最高数字的总和为17,与之前的19相比.我可以做的第二次交换是来自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.所以即使当前的安排是最好的,它仍然会交换一些值.当前的安排是最好的,我早先打破了.这样做的原因是因为除了TWO之外我正在测试所有测试用例!猜猜什么更令人讨厌,一个来自每个任务!:(所以我意识到必须完成所有K开关.但是即使现在我得到2个测试用例错了,必须有一些我忽略的东西.

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

顺便说一下,任务1的K = 1.

Answer 1

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

此外，您还进行了大量的矢量复制，这使得代码效率低下。即使代码的逻辑是正确的，您的代码也不会超过时间限制，因为您的方法是 O(n ² )。

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

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

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

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;
}