在两个向量之间交换值，使得两个向量的max_elements的和最小 [英] Swapping values between two vectors so that sum of max_elements of two vectors is minimum

问题描述

这是Codechef的问题，但请承认我。
https://www.codechef.com/ZCOPRAC/problems/ZCO16001

比赛是为了筹备在印度举行的区域计算奥林匹克竞赛，所以它不是一个竞争性比赛，我从中赚取这样的东西。只需要一点帮助看看我的代码是什么，因为我有一种感觉，我忽略了一些大而愚蠢的东西。 ：P

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

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

我的方法很简单。从Vector1（V1）中取最高的数字，并从V2中最低的数字进行交换。添加每个的最高值。做同样的，但这次交换最高的数字从V2与最低的从V1。添加每个的最高值。

例如：

p> V1 = 5 6 7 9

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

V1 = 5 6 7 4

V2 = 9 10 5 9

与早期的19相比，最高数字为17的总和。我可以做的第二个交换是从V2 5从V1给出：

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  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  cin>> X; 
 s1.push_back（x）; 
} 
 for（unsigned int i = 0; 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 
} 
  

请注意，这样做都会交换ie。是最好的，它仍然会交换一些价值。早些时候我打破了当前的安排是最好的。这样做的原因是因为我得到所有测试用例，除了两个！猜猜什么更恼人，一个是从每个任务！ （
）所以我意识到必须完成所有的K开关，但即使现在我得到2个测试错误，一定有一些我忽略了。

任何想法是什么？
链接到解决方案： https://www.codechef.com / viewsolution / 11574501

而btw，任务1的K = 1。

解决方案

你的代码的问题是你在交换之间改变数组，因此有可能在数组之间来回切换一个项目。我的意思是在第一次交换你放置元素 x 从array1到array2，并在下一个交换，它是可能的，你再次交换它。

还有你做了很多矢量复制使代码低效即使你的代码的逻辑正确，你的代码也不会超过时间限制，因为你的方法是O（n ² ）。

< hr>

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

• 将两个数组排序


• 为 x 从0到 k
  
  
  
  
  • 假设交换 x 第一个数组的最小元素为 x
  
  
  • result = min（result，max（result，max（first array）+ max（second array））
  
  
  
  
  • result = min（result，max（result））将第一个数组的最大元素与第二个数组的最小元素 x ，max（first array）+ max（second array））
  
  


• / li>
  

由于两个数组都排序，你可以在进行一次比较之后找到数组的最大元素。

  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] -1]）$ ​​b $ bx = 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]）$ ​​b $ b ... 
  
 
 
 
这是被接受的实现：
  #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>>温度
 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] ]）; 
 result = min（result，t）; 
} 
 
 cout<<结果< endl 
} 
  
 
This is a question from Codechef but please bear with me.
https://www.codechef.com/ZCOPRAC/problems/ZCO16001

The contest is for the preparation of the Zonal Computing Olympiad held in India, so its not a competitive contest from which I'd earn something as such. Just need a little help to see what is wrong with my code, because I have a feeling I've overlooked something big and stupid. :P

So basically the question is summed up as this.

  
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.
My approach was simple. Take the highest number from Vector1 (V1) and swap it with the lowest from V2. Add the highest values of each. Do the same, but this time swap the highest number from V2 with the lowest from V1. Add the highest values of each. The better swapping will be the one with the lowest sum and continue from there K times.

So for example:

V1 = 5 6 7 9

V2 = 9 10 5 4

In this case, if K = 1
I would first swap V1's 9 with V2's 4. This gives:

V1 = 5 6 7 4

V2 = 9 10 5 9

Sum of highest number as 17, as compared to earlier's 19. The second swap I could do is 10 from V2 with 5 from V1 giving:

V1 = 10 6 7 4

V2 = 9 5 5 9

This gives sum as 19, so better was the first swap and the output should be 17.

Here is my solution:
#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;
}
Please note that this does all swaps i.e K. So even if the current arrangement was the best, it would still swap some values. Earlier I was breaking when the current arrangement was the best. The reason for doing this is because I was getting all test cases right except TWO! And guess what was even more annoying, one was from each task! :( 
So I realised it must be necessary to complete all K switches. However even now I am getting 2 testcases wrong, there must be something I have overlooked. 

Any idea what it is?
Link to solution: https://www.codechef.com/viewsolution/11574501

And btw, Task 1 has K = 1.
解决方案
The problem with your code is you change the arrays between swaps and therefore there is the possibility of swapping one item back and forth between arrays. I mean in the first swap you place element x from array1 to array2 and in the next swap it is possible that you swap it back again.

Also you do a lot of vector copying which make the code inefficient. Even if the logic of your code was correct your code wouldn't have passed the time limit because your approach is O(n2).



First note that optimal answer is when all the elements in one array are bigger than all the elements in the other array.  


Sort both arrays
for  x  from 0 to k 


hypothetically swap x minimum elements of first array with x maximum elements of the second array.
result = min(result, max(result, max(first array) + max(second array) )
hypothetically swap x maximum elements of first array with x minimum elements of the second array.
result = min(result, max(result, max(first array) + max(second array) )

result will hold the final answer


Since both arrays are sorted you can find maximum elements of the arrays after hypothetical swap with one comparison.
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])
...
This is the accepted implementation:
#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;
}


                        
这篇关于在两个向量之间交换值，使得两个向量的max_elements的和最小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！