题解 | #[NOIP2009]分数线划定#

package main

import (
    .    "fmt"
    "io"
    "bufio"
    "os"
)

type Student struct {
    id, score int
}

func gt(s1,s2 Student) bool{
    if s1.score > s2.score {
        return true
    }else if s1.score == s2.score && s1.id < s2.id {
        return true
    }
    return false
}

// 快排找到分数线
func getScoreLine(arr []Student, m, l, r int)int{
    if l <= r {
        i, L, R := l, l -1, r + 1
        x := arr[l + (r -l) / 2]
        for i != R {
            if arr[i].score < x.score {
                R--
                arr[R],arr[i] = arr[i],arr[R]
            }else if arr[i].score > x.score {
                L++
                arr[L],arr[i] = arr[i],arr[L]
                i++
            }else {
                i++
            }
        }
        if m <= L {
            return getScoreLine(arr, m, l, L)
        }else if m >= R {
            return getScoreLine(arr, m, R, r)
        }else {
            return arr[m].score
        }
    }else {
        return -1
    }
}


func NC16625(_r io.Reader, _w io.Writer) {
    in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
    defer out.Flush()
    var n,m int
    Fscan(in, &n, &m)
    arr := make([]Student, n)
    for i:=0; i<n; i++{
        Fscan(in, &arr[i].id, &arr[i].score)
    }
    score := getScoreLine(arr, (m * 3 / 2) - 1, 0, n - 1)
    // 二分截取分数线符合条件的所有人
    l, r := 0, n - 1
    for l <= r {
        mid := l + (r - l) / 2
        if arr[mid].score >= score {
            l = mid + 1
        }else {
            r = mid - 1
        }
    }
    arr = arr[:l]
    Fprintln(out, score, l )
    
    // 堆化 - 大根堆
//     for i := len(arr) - 1; i >= 0; i-- {
//         siftDown(arr, i, len(arr))
//     }
    for i := 0; i < len(arr); i++ {
        siftUp(arr,i)
    }
  
    for i := len(arr) - 1; i >= 0; i-- {
        Fprintln(out, arr[0].id, arr[0].score)
        arr[0] = arr[i]
        siftDown(arr, 0, i)
    }
    
}
func siftDown(h []Student, i, end int) {
    l, r := i * 2 + 1, i * 2 + 2
    if l < end { 
        largest := i
        
        if gt(h[l], h[i]) {
            largest = l
        }
        if r < end && gt(h[r],h[largest])  {
           largest = r
        }
        
        if largest == i {
            return
        }
        h[i], h[largest] = h[largest], h[i]
        siftDown(h, largest, end)
    }
}

func siftUp(h []Student, i int) {
    for i != 0 && gt(h[i], h[(i-1)/2]) {
        h[i],h[(i-1)/2]=h[(i-1)/2],h[i]
        i=(i-1)/2
    }
}

func main() {
    NC16625(os.Stdin, os.Stdout)
}