[Kotlin] Korean Coding Test - Programmers - Delivery And Collection Of Parcels

Question

Link

You want to deliver the package to n houses arranged in a row. Everything to be delivered is delivered in the same size recycled delivery box, and I'm trying to collect empty recycled delivery boxes as I go around.

All the packages to be delivered are stored in a recycling courier box and stored in a warehouse, and the i-th house is a distance i from the warehouse. The i-th house is also a distance j - i from the j-th house. (1 ≤ i ≤ j ≤ n)

Trucks can carry up to cap recycled delivery boxes. Trucks pick up empty recycling packages and drop them off at the warehouse, leaving the warehouse and delivering them to each house. When you know the number of recycling delivery boxes for each home and the number of empty recycling delivery boxes to collect, you're trying to find the minimum travel distance for a single truck to complete all deliveries and collections and return to the warehouse. When delivering and collecting to each home, you can deliver and collect as many packages as you want.

The parameters are an integer cap representing the maximum number of recycling courier boxes that can be loaded on a truck, an integer n representing the number of houses to be delivered, a one-dimensional integer array delivery containing the number of recycling courier boxes to be delivered to each house and a one-dimensional integer array pickups containing the number of empty recycling courier boxes to be collected in each house. At this time, complete the solution function so that the minimum travel distance that can be returned to the warehouse after completing all delivery and collection with one truck.

Restrictions

1 ≤ cap ≤ 50

Length of 1 ≤ n ≤ 100,000 deliveries = length of pickups = n

• Deliveries[i] represents the number of recycled delivery boxes to be delivered to the i+1st home.
• Pickups[i] represents the number of empty recycling delivery boxes to be collected from the i+1st home.
• Elements of 0 ≤ delivery ≤ 50
• Elements of 0 ≤ pickups ≤ 50

The initial location of the truck is the warehouse.

Input/Output Example

Input/Output Example #1

• Input
• cap: 4
• n: 5
• deliveries: [1, 0, 3, 1, 2]
• pickups: [0, 3, 0, 4, 0]
• Output: 16

Input/Output Example #2

• Input
• cap: 2
• n: 7
• deliveries: [1, 0, 2, 0, 1, 0, 2]
• pickups: [0, 2, 0, 1, 0, 2, 0]
• Output: 30

Solve

If the package to be delivered and collected is in the i-th house, it must go to the i-th house at least once.

• You have to go back and forth from the warehouse to the i-th house.

If there is an amount that cannot be processed at a time, you must return and return until all is processed.

• You have to find the minimum travel distance, so visit the house that is the furthest away.

Delivery and collection can be handled simultaneously as many as caps while departing from the warehouse and coming back.

• From the furthest house, deliver in reverse order and fill the empty space with collection packages.

Code

class Solution {
    fun solution(cap: Int, n: Int, deliveries: IntArray, pickups: IntArray): Long {
        var answer: Long = 0

        var delivery = 0 // Remaining Courier Box
        var pickup = 0 // Remaining Collection Box

        // You have to go back and forth no matter what, so you have to go back from the furthest house
        for (i in n - 1 downTo 0) {
            // Amount to be processed for delivery and collection
            delivery += deliveries[i]
            pickup += pickups[i]
            // Return until delivery and collection are complete
            while (delivery > 0 || pickup > 0) {
                delivery -= cap
                pickup -= cap
                // Return to the i+1st house and the warehouse
                answer += (i + 1) * 2
            }
        }

        return answer
    }
}

TEST 1 〉	Pass (0.12ms, 58.3MB)
TEST 2 〉	Pass (0.06ms, 62.3MB)
TEST 3 〉	Pass (0.04ms, 62.1MB)
TEST 4 〉	Pass (0.05ms, 60.9MB)
TEST 5 〉	Pass (0.04ms, 61.4MB)
TEST 6 〉	Pass (0.04ms, 60.6MB)
TEST 7 〉	Pass (0.12ms, 62.3MB)
TEST 8 〉	Pass (0.16ms, 61.8MB)
TEST 9 〉	Pass (0.37ms, 63.2MB)
TEST 10 〉	Pass (0.60ms, 63.8MB)
TEST 11 〉	Pass (0.22ms, 65MB)
TEST 12 〉	Pass (0.28ms, 63.1MB)
TEST 13 〉	Pass (0.21ms, 63.9MB)
TEST 14 〉	Pass (0.16ms, 65.1MB)
TEST 15 〉	Pass (2.83ms, 69.6MB)
TEST 16 〉	Pass (12.00ms, 69.6MB)
TEST 17 〉	Pass (4.62ms, 69.6MB)
TEST 18 〉	Pass (3.27ms, 68.3MB)
TEST 19 〉	Pass (3.58ms, 69.6MB)
TEST 20 〉	Pass (3.28ms, 69.5MB)