题解 | #奖学金#

golang 贪心解法

package main

import (
    "fmt"
    "io"
    "sort"
)

type score_hour struct {
    score int
    hour  int
}

func main() {
    var n, r, avg int
    for {
        _, err := fmt.Scan(&n, &r, &avg)
        if err == io.EOF {
            break
        }
        v := make([]score_hour, 0)

        var temp score_hour

        for n > 0 {
           n--
            fmt.Scan(&temp.score, &temp.hour)
            v = append(v, temp)
        }
        // 需要的总分
        target := len(v) * avg
        // 当前成绩
        score_cur := 0
        time := 0
        for i := 0; i < len(v); i++ {
            score_cur += v[i].score
        }
        if score_cur >= target {
            fmt.Println(0)
        } else {
            sort.Slice(v, func(i, j int) bool {
                if v[i].hour < v[j].hour {
                    return true
                }
                return false
            })
            for i := 0; i < len(v); i++ {
                // 该课程获得满分求当前总分数
                score_cur += (r - v[i].score)
                if score_cur >= target {
                    //当前分数超过目标成绩说明该课程不得满分也已经满足奖学金条件   
                    score_cur -= (r - v[i].score)
                    time += (target - score_cur) * v[i].hour
                    fmt.Println(time)
                    break
                } else {
                    time += (r - v[i].score) * v[i].hour
                }
            }
        }
    }
}