英文:
Adding two arrays into one
问题
我有两个大小为n的数组（a和b），都是正整数。
a= [a1…..an] b= [b1….bn]
我想将它们存储在数组c中，c也是大小为n的数组。
c=[c1…..cn]
在c中，我想将来自a的一个元素与来自b的一个元素相加（每个元素只能使用一次），比如说c中的第一个元素是a1+b3。
简单的例子：
n=4 a=[a1,a2,a3,a4] b=[b1,b2,b3,b4]
一种方式是：
c=[a1+b2,b3+a4,a2+b1,a3+b4]
问题是，我希望以尽可能均匀分布的方式添加它们，一个理想的情况是c变为：
c=[5,5,5,5]
但是a和b中的数字可能不匹配，因此它们可能不会变得均匀，所以我希望它尽可能接近均匀。
我试图找到一种方法，使c中的最大数与最小数的差尽可能小（在尽量均匀地组合后）。在我上面的最佳示例中，差值是5-5=0，这是最理想的，因为0是我希望实现的最小差值。在其他情况下，差值可能是6-5=1，这可能是我在那种情况下能获得的最小值。
我的方法是将数组a按升序排列，数组b按降序排列，然后将它们与相同的元素组合。我不确定这是否是最佳方法或最快速的方法。我希望我的代码（使用Python编写）能够运行得很快。我无法想出更好的方法，以便能够更均匀地分配它们。是否有更好的方法来解决这个问题？我非常感谢您提供的所有建议！谢谢！
在尝试以其中一个数组升序排列，另一个数组降序排列的方式来解决它时，可能已经存在一种更好的解决方法，我没有考虑到。谢谢您的阅读！
英文:
I have two arrays (a and b) of size n, (positive whole numbers)
a= [a1…..an]
b= [b1….bn]
I want to store them in array c, also an array of size n
c=[c1…..cn]
where I add one element from a plus one element from b (each used once) into c, lets say the first element in c is combining a1+b3
Quick example:
n=4
a=[a1,a2,a3,a4]
b=[b1,b2,b3,b4]
one way could be:
c=[a1+b2,b3+a4,a2+b1,a3+b4]
The problem is that I want to add them in a way so that the elements in c become as evenly distributed as possible,
One ideal case would be that c came out as:
c=[5,5,5,5]
but the numbers in a and b might not match up so they become even, so I want it to come as close to even as possible.
I an trying to find a way so that the difference between the biggest number in c minus the smallest number in c (after being combined as evenly as I can) to be as small as possible. In my optimal example above that would be 5-5=0 which is most optimal since 0 is the smallest minimum difference I want to achieve. Some other case with other numbers might come out as 6-5=1, which might be the smallest I could get in that situation
My way of going would be to sort array a in ascending order and my array b in descending order,and then combining them with the same element that they are in. Im not sure if this is the best way or the fastest to do this in, I want my code (doing it with python) to be fast. I cant come up with a better way where I could distribute them more evenly,any clue if there are better ways to solve this problem? I really appreciate all advice I could get! Thank you
When trying to solve it in a way where one of the arrays is ascending, and the other one being descending, there might already exist an algorithm that solves it better that I have not thought of. Thank you for reading!
答案1
得分: 3
你的算法既正确又快速。只是证明它的最优性有点棘手。
我们可以通过证明以下两个结果来实现这一点。
a和b的任何其他匹配都会导致至少与你的一样大的最大值。a和b的任何其他匹配都会导致至少与你的一样小的最小值。
结论是，任何其他匹配都必须具有至少与你的一样大的最大值和一样小的最小值。从而证明了你的匹配是最优的。
现在让我们看看第一部分。升序排序 a，降序排序 b。找到使 c[i] = a[i] + b[i] 最大的 i。假设 m 是任何其他匹配，其中我们正在匹配 a[j] + b[m[j]]。注意，m[1], ..., m[n] 是 1, ..., n 的排列。
如果 a[i] + b[m[i]] >= a[i] + b[i]，那么第一部分成立。
如果 a[i] + b[m[i]] < a[i] + b[i]，那么 b[m[i]] < b[i]，因此我们必须有 i < m[i]。现在在范围 i+1, ..., n 中有 n-i 个数字。m 将范围内的某个东西映射到该范围内。因为 m 是一个排列，根据鸽巢原理，m 必须将范围内的某个东西映射到范围外。
换句话说，必须存在一个 j > i，使得 m[j] <= i。但现在 a[i] <= a[j]，b[i] <= b[m[j]]，因此 a[i] + b[i] <= a[j] + b[m[j]]。因此第一部分再次成立。
这就完成了第一部分的证明。
第二部分的证明类似。不过现在 a[i] + b[i] 达到了最小值，m[i] < i，存在一个 j < i，使得 i <= m[j]，a[j] <= a[i]，b[m[j]] <= b[i]，且 a[j] + b[m[j]] <= a[i] + b[i]。
正如前面所指出的，第一部分和第二部分的结合意味着你已经最小化了最小值和最大值之间的差异。
英文:
Your algorithm is both correct and fast. It is just proving it that is optimal which is tricky.
We can do this by proving the following two results.
- Any other matching of
aandbwill lead to a maximum at least as big as yours. - Any other matching of
aandbwill lead to a minimum at least as small as yours.
And the conclusion is that any other matching must have a maximum-minimum at least as big as yours. From which yours must be optimal.
Now let's look at part 1. Sort a ascending, and b descending. Find the i such that c[i] = a[i] + b[i] is a maximum. Suppose that m is any other matching where we're matching up a[j] + b[m[j]]. Note that m[1], ..., m[n] is a permutation of 1, ..., n.
If a[i] + b[m[i]] >= a[i] + b[i] then part 1 is true..
If a[i] + b[m[i]] < a[i] + b[i] then b[m[i]] < b[i] and so we must have i < m[i]. Now there are n-i numbers in the range i+1, ..., n. m maps something out of that range into that range. Because m is a permutation, by the pigeonhole principle, m must map something in that range, out of that range.
In other words there must be a j > i such that m[j] <= i. But now a[i] <= a[j] and b[i] <= b[m[j]] and therefore a[i] + b[i] <= a[j] + b[m[j]]. And so part 1 is true again.
That concludes the proof of part 1.
The proof of part 2 is similar. Except now a[i] + b[i] is at a minimum, m[i] < i, there is a j < i with i <= m[j], a[j] <= a[i], b[m[j]] <= b[i], and a[j] + b[m[j]] <= a[i] + b[i].
And as noted, part 1 and part 2 together implies that you've minimized the difference between the minimum and maximum.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论