白駿1461号:図書館-Swift

https://www.acmicpc.net/problem/1461
難易度-金貨5🥇
アルゴリズム分類:グリディ
🧐 質問へのアクセス
まず最良の状況を考え出してこそ,問題の解決に着手することができる.
最初に思いついたのは、現在位置に最も近い本棚へのアクセスを続けることです.
もちろん、これは最小値ではありません.
本当に知らなかったので悩んで他の人の解答を見ました
明快だと思いますが、考えにくいです.
ex
n = 7, m = 2
-37、2、-6、-39、-29、11、および-28入力します.
配列を負、正に分割し、絶対値を取って逆順に並べます.
pos = [2,11]
neg = [6, 28, 29, 37, 39]
neg配列については,それぞれ2つずつ切断して考えてみる.
0 -> 37,39 -> 0
0 -> 28, 29 -> 0
0 -> 6 -> 0
(39 + 29 + 6) * 2 = 148
pos配列に同様に適用すると、
0 -> 2, 11 -> 0
(11 * 2) = 22
全部で170冊の本を移動し、すべての本を持ち帰れば、原点に戻る必要はありません.
だから、最低限にしたいなら、最後に37、38を訪問すればいいのではないでしょうか.
最終的には170-39=131の答えが得られます!
コード#コード#
1 m切り離して返却する
最大距離値のみansに追加できます.
意味がないため、他の値は破棄されます.

while !positiveArr.isEmpty {
    ans += positiveArr.removeLast()
    for _ in 0 ..< m-1 {
        _ = positiveArr.popLast()
    }
}

while !negativeArr.isEmpty {
    ans += negativeArr.removeLast()
    for _ in 0 ..< m-1 {
        _ = negativeArr.popLast()
    }
}

完全なコード

//1461번 도서관
let t = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,m) = (t[0],t[1])
let books = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted()

var positiveArr: [Int] = []
var negativeArr: [Int] = []

books.forEach { pos in
    if pos > 0 {
        positiveArr.append(pos)
    } else {
        negativeArr.append(pos * -1)
    }
}
negativeArr = negativeArr.reversed()

let maxLen = max(positiveArr.max() ?? 0, negativeArr.max() ?? 0)
var ans = 0

while !positiveArr.isEmpty {
    ans += positiveArr.removeLast()
    for _ in 0 ..< m-1 {
        _ = positiveArr.popLast()
    }
}

while !negativeArr.isEmpty {
    ans += negativeArr.removeLast()
    for _ in 0 ..< m-1 {
        _ = negativeArr.popLast()
    }
}

print(ans * 2 - maxLen)

一行の評価:グリディは難しすぎる