package main import . "fmt" import . "os" import bf "bufio" import . "sort" import "math/rand" func main() { rd := bf.NewReader(Stdin) var n int Fscan(rd,&n) a := make([]int, n) for i := range a { Fscan(rd,&a[i]) } b := make([]int, n) for i := range b { Fscan(rd,&b[i]) } x, fx := solve1(n, a, b) Println(x, fx) } func abs(a int) int { return max(a, -a) } func solve1(n int, a, b []int) (int, int) { table := make([]int, 2e6+1) s, t := 0, 0 f := 0 for i := 0; i < n; i++ { table[a[i]+1e6] += b[i] f += b[i]*abs(a[i]-(-1e6)) t += b[i] } xMin := int(-1e6) fMin := f for x := xMin; x < 1e6; x++ { e := table[x+1e6] s += e t -= e f += s - t if f < fMin { xMin = x+1 fMin = f } } return xMin, fMin } func solve2(n int, a, b []int) (int, int) { index := make([]int, n) for i := range index { index[i] = i } Slice(index, func(i, j int) bool { return a[index[i]] < a[index[j]] }) s, t := 0, 0 for _, e := range b { t += e } for _, i := range index { s += b[i] t -= b[i] if s >= t { x := a[i] f := 0 for k := 0; k < n; k++ { f += b[k] * abs(a[k] - x) } return x, f } } return 0,0 } func init() { check() } func check() { for t := 0; t < 10; t++ { n := rand.Intn(20)+10 a := make([]int, n) for i := range a { a[i] = rand.Intn(2*n)-n } b := make([]int, n) for i := range b { b[i] = rand.Intn(3)+1 } x1,f1 := solve1(n, a, b) x2,f2 := solve2(n, a, b) if f1 != f2 { println("n=",n) println("a=",Sprint(a)) println("b=",Sprint(b)) println("x1=",x1) println("f1=",f1) println("x2=",x2) println("f2=",f2) panic("wrong") } } println("OK") } /* 考察 X = min(A) としてf(X)を計算する このとき f(X+1) について考える すべてのAと差分が 1 だけ変化する A[i] < X+1 のとこは B[i] だけ増える A[i] >= X+1 のとこは B[i] だけ減る つまり、適当な X をとって +1 すると A[i] < X+1 な位置にあるものに対応する B[i] の合計の分だけ f が増える A[i] >= X+1 な位置にあるもに対応する B[i] の合計の分だけ f が減る 前者のB[i]の合計をS、後者のB[i]の合計をT、とすると Xを+1すると、fはS増えて、fはT減る、 Xがある点A[i]に到達するとS,Tが変化し SはB[i]増えて、TはB[i]減る S < T になる X の領域は f は減少して (X=min(A)はこの領域かも) S = T になる X の領域は f は変化せず  S > T になる X の領域は f は増加する (X=max(A)はこの領域かも) つまり S < T から S > T にかわるあたりがfを最小にするXの位置 S = T の領域が存在すればその領域のどこでもfを最小にするXの位置のはず いずれにせよA[i]のどれかがfを最小にするXとして使える S=Tとなる領域においては領域内の任意実数をXとしても使えるが、なんの意味が A[i]は10^6と大きくないため X=min(A)からX=max(A)までXを+1ずつ動かしてf(X)を変化さて最小を求めるでもいいし Bの累積和をとって、S,Tの大小関係が逆転する位置X=A[i]を特定してf(X)を計算するでもいいし そんな感じ? */