type
status
date
slug
summary
tags
category
icon
password
🔎 Problem
Rearrange an array of integers so that the calculated value U is maximized. Among the
arrangements that satisfy that test, choose the array with minimal ordering. The value of U
for an array with n elements is calculated as :
U = arr[1]×arr[2]×(1÷arr[3])×arr[4]×...×arr[n-1] × (1÷arr[n]) if n is odd
or
U = arr[1]×arr[2]×(1÷arr[3])×arr[4]×...×(1÷arr[n-1]) × arr[n] if n is even
The sequence of operations is the same in either case, but the length of the array, n,
determines whether the calculation ends on arr[n] or (1÷arr[n]).
Arrange the elements to maximize U and the items are in the numerically smallest possible
order.
example_arrs = [21, 34, 5, 7, 9]
result = [9, 21, 5, 34, 7]
max = 183.6
📝 Critical process
According to the title, we need to reach two conditions
Condition 1: Find the largest U-value
Condition 2: If condition 1 is met, sort the list in the smallest order
Analyzing the equation for U shows that:
1. All elements are multiplied, so if the value of an element is fixed,
changing the position of an element in the equation will not change the result.
2. From 1, the size of the result U depends on the size of the elements in the equation
3. Further, it is clear from the equation that the size of an element is determined only by its position,
starting at the odd bits of the equation(from the index bit index >= 2), the element is changed to
(1/element itself), and remains unchanged at the event bits, so to find the largest U, one should make
the elements at these odd bits as large as possible.
4. By the nature of division, 1 / x should be as large as possible, so the base x should be as small as possible,
so you should use the smallest element of the list as the x-value as much as possible
5. In analyzing the equation from the question, it is clear that the number of elements that need to be converted to their own fractions m:
m = {
0, n <=2,
(n - 3) / 2 + 1 , n>2, if n is odd
(n-2) / 2, n>2, if n is even
}
Code implementation
- 作者:刘爽 Lucas
- 链接:https://github.com/Enternalcode/article/find-max-u
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。