AcWing 125. 耍杂技的牛
原题链接
中等
作者:
Sam_2
,
2020-10-04 21:21:06
,
所有人可见
,
阅读 370
package main
import (
"fmt"
"math"
"sort"
)
const N int = 50010
var s [N]int
var w [N]int
type Pair struct {
s int
w int
}
type PairArray []*Pair
func (p PairArray) Len() int {
return len(p)
}
func (p PairArray) Less(i, j int) bool {
return p[i].s + (p)[i].w < (p)[j].s + (p)[j].w
}
func (p PairArray) Swap(i, j int) {
(p)[i], (p)[j] = (p)[j], (p)[i]
}
func main() {
var n int
fmt.Scanf("%d", &n)
mapval := make([]*Pair, 0, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d", &s[i])
fmt.Scanf("%d", &w[i])
mapval = append(mapval, &Pair{s:s[i], w:w[i]})
}
sort.Sort(PairArray(mapval))
res := math.MinInt32
sum := 0
for i := 0; i < n; i++ {
if res < sum - mapval[i].w {
res = sum - mapval[i].w
}
sum += mapval[i].s
}
fmt.Printf("%d\n", res)
}