[伯俊]1744番の手を縛る

17148 ワード
グリディ テキストリンク
伯準-1744号手を縛る
質問する
長さNの数列が与えられると、その和が要求される.しかし、私はその数列の和を全部足して求めるだけでなく、数列の2つの数を縛りたいと思っています.数を縛ろうとすると、どこにでも縛ることができます.しかし、同じ位置にある数字(自分)を縛ることはできない.そして、ある数を縛って、数列の和を求める場合は、縛った数を乗算して加算します.
例えば、ある数列が{0,1,2,4,3,5}の場合、その数列の和のみが0+1+2+4+3+5=15となる.ただし、2と3をバンドルし、4と5をバンドルすると、0+1+(23)+(45)=27が最大値となります.
数列のすべての数値は、1回のみバインドするか、1回バインドしない必要があります.
数列を指定する場合は、数列の各数を適切に組み合わせて最大にするプログラムを作成します.
方法
最大角度の検索方法
a>1&b>1を掛けると1より大きいので縛る
a<1&b<1の場合、1以上を乗じて縛る
そこで,sortDescendingを行った後に,断面積値が大きい場合から正の値と1未満の場合をチェックして加算する.
間に合わなかった分を入れて問題を解決した.
コード#コード#
import java.lang.Math.hypot
import java.util.*

class IO1774 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
    fun getRow() = br.readLine().split(" ").map{ it.toInt() }
}

fun main() {
    val io = IO1774()
    val (N, M) = io.getRow()

    fun getArray(num: Int): Array<List<Int>> {
        return Array(num) {
            io.getRow()
        }
    }

    val positionArr = getArray(N)
    val distanceArr = Array(N) { Array(N) { Double.MAX_VALUE } }

    fun getDistance(p1: List<Int>, p2: List<Int>): Double {
        val (x1, y1) = p1
        val (x2, y2) = p2
        return hypot((x1-x2).toDouble(), (y1-y2).toDouble())
    }

    for (i in 0 until N) {
        val p1 = positionArr[i]
        for (j in i+1 until N) {
            val p2 = positionArr[j]
            val dis = getDistance(p1, p2)
            distanceArr[i][j] = dis
            distanceArr[j][i] = dis
        }
    }

    val visited = Array(N) { false }

    repeat(M) {
        val (p1, p2) = io.getRow()
        distanceArr[p1-1][p2-1] = 0.0
        distanceArr[p2-1][p1-1] = 0.0
    }

    data class Edge(val source: Int, val dest: Int, val cost: Double)
    val pq = PriorityQueue<Edge>(compareBy { it.cost })
    for(row in 1 until N) {
        pq.add(Edge(0, row, distanceArr[0][row]))
    }
    var answer: Double = 0.0
    var edge = 0
    visited[0] = true
    while (edge < N - 1) {
        val e = pq.poll()
        val (sour, dest, cost) = e

        if (visited[dest]) continue
        visited[dest] = true
        answer += cost
        edge++

        if (cost == Double.MAX_VALUE) continue

        for (row in 0 until N) {
            if (dest == row) continue
            pq.add(Edge(dest, row, distanceArr[dest][row]))
        }
    }
    io.write(String.format("%.2f", answer))
    io.close()
}
Affel 15日目1/14(金)
文脈APIを例証してください