Es scheint, dass die Punktzahl, wenn a i </ sub> in absteigender Reihenfolge und b i </ sub> in aufsteigender Reihenfolge sortiert ist, immer der Maximalwert ist, aber der gleiche Maximalwert verwendet wird. Wenn es mehr als eine gibt, kann ich mir keine Möglichkeit vorstellen, wie viele zu lösen. Wenn Sie sorgfältig darüber nachdenken, N ≤ 9 und 9! ≒ 3,6 × 10 5 </ sup>, konnte ich alle ausprobieren.
from itertools import permutations
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = {}
for x in permutations(a):
t = 0
for i in range(N):
t += max(x[i] - b[i], 0)
d.setdefault(t, 0)
d[t] += 1
print(d[max(d)])
Die Wahrscheinlichkeit ist die Anzahl von N × M-Kombinationen, die C überschreiten, geteilt durch N × M. Wenn b sortiert ist, überschreitet die Kombination mit a i </ sub> C. Die Anzahl von i </ sub> kann durch * O * (log M </ i>) berechnet werden, also * O * ((* N * + * M *) log M. </ i>) und kann gelöst werden. Sie können a sortieren.
from bisect import bisect_left
N, M, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
c = 0
for x in a:
t = ((C + 1) + x - 1) // x
c += M - bisect_left(b, t)
print(c / (N * M))
Da es eine Chance ist, später eine große Punktzahl zu erzielen, scheint es, dass der Maximalwert darin besteht, a in aufsteigender Reihenfolge auszugeben. Es ist schwierig, die Anzahl der Blätter, die kleiner als a i </ sub> sind, aus dem akkumulierten b zu ermitteln Wenn Sie verwenden möchten, müssen Sie die Sortierung beibehalten, und wenn Sie jedes Mal naiv sortieren, ist dies * O * (* N * 2 </ sup> log N </ i>) und natürlich TLE. Sortiert AC kann durchgeführt werden, indem das Array in zwei kleine und große Arrays unterteilt wird und jedes Mal nur das kleinere sortiert wird, wodurch der Rechenaufwand verringert wird.
from bisect import bisect_left
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
t0 = []
t1 = []
result = 0
for i in range(N):
result += bisect_left(t0, a[i])
t1.append(b[i])
t1.sort()
result += bisect_left(t1, a[i])
if len(t1) == 300:
t0.extend(t1)
t0.sort()
t1.clear()
print(result)
Nachtrag: Es scheint, dass die angenommene Lösung Koordinatenkomprimierung + BIT war, also habe ich sie immer noch gelöst.
def bit_add(bit, i, x):
i += 1
n = len(bit)
while i <= n:
bit[i - 1] += x
i += i & -i
def bit_sum(bit, i):
result = 0
i += 1
while i > 0:
result += bit[i - 1]
i -= i & -i
return result
def bit_query(bit, start, stop):
if start == 0:
return bit_sum(bit, stop - 1)
else:
return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = {j: i for i, j in enumerate(sorted(set(a + b)))}
bit = [0] * len(t)
a.sort()
result = 0
for i in range(N):
bit_add(bit, t[b[i]], 1)
result += bit_query(bit, 0, t[a[i]])
print(result)
Sie müssen keine einmalige Mautgebühr zahlen. Die DP-Tabelle vor und nach der Verwendung des Rechts wurde in die Suche nach Breitenpriorität unterteilt, und AC wurde durchgeführt. Die Dikstra-Methode wurde nicht benötigt. Wenn der Anfangswert auf "math.MaxInt64" gesetzt ist, läuft sie über. Als ich starb und math.MaxInt32 machte, war es diesmal zu klein und ich WA und entschied mich für math.MaxInt64 >> 1.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
defer flush()
N := readInt()
M := readInt()
c := make([][]int, N)
for i := 0; i < N; i++ {
c[i] = make([]int, N)
}
for i := 0; i < M; i++ {
h := readInt() - 1
w := readInt() - 1
c[h][w] = readInt()
}
dpa := make([][]int, N)
dpb := make([][]int, N)
for i := 0; i < N; i++ {
dpa[i] = make([]int, N)
dpb[i] = make([]int, N)
for j := 0; j < N; j++ {
dpa[i][j] = math.MaxInt64 >> 1
dpb[i][j] = math.MaxInt64 >> 1
}
}
dpa[0][0] = 0
q := make([][3]int, 0)
q = append(q, [3]int{0, 0, 0})
for len(q) != 0 {
y := q[0][0]
x := q[0][1]
t := q[0][2]
q = q[1:]
if t == 0 {
if y != 0 {
if dpa[y-1][x] > dpa[y][x]+1+c[y-1][x] {
dpa[y-1][x] = dpa[y][x] + 1 + c[y-1][x]
q = append(q, [3]int{y - 1, x, 0})
}
if c[y-1][x] > 0 {
if dpb[y-1][x] > dpa[y][x]+1 {
dpb[y-1][x] = dpa[y][x] + 1
q = append(q, [3]int{y - 1, x, 1})
}
}
}
if y != N-1 {
if dpa[y+1][x] > dpa[y][x]+1+c[y+1][x] {
dpa[y+1][x] = dpa[y][x] + 1 + c[y+1][x]
q = append(q, [3]int{y + 1, x, 0})
}
if c[y+1][x] > 0 {
if dpb[y+1][x] > dpa[y][x]+1 {
dpb[y+1][x] = dpa[y][x] + 1
q = append(q, [3]int{y + 1, x, 1})
}
}
}
if x != 0 {
if dpa[y][x-1] > dpa[y][x]+1+c[y][x-1] {
dpa[y][x-1] = dpa[y][x] + 1 + c[y][x-1]
q = append(q, [3]int{y, x - 1, 0})
}
if c[y][x-1] > 0 {
if dpb[y][x-1] > dpa[y][x]+1 {
dpb[y][x-1] = dpa[y][x] + 1
q = append(q, [3]int{y, x - 1, 1})
}
}
}
if x != N-1 {
if dpa[y][x+1] > dpa[y][x]+1+c[y][x+1] {
dpa[y][x+1] = dpa[y][x] + 1 + c[y][x+1]
q = append(q, [3]int{y, x + 1, 0})
}
if c[y][x+1] > 0 {
if dpb[y][x+1] > dpa[y][x]+1 {
dpb[y][x+1] = dpa[y][x] + 1
q = append(q, [3]int{y, x + 1, 1})
}
}
}
} else {
if y != 0 {
if dpb[y-1][x] > dpb[y][x]+1+c[y-1][x] {
dpb[y-1][x] = dpb[y][x] + 1 + c[y-1][x]
q = append(q, [3]int{y - 1, x, 1})
}
}
if y != N-1 {
if dpb[y+1][x] > dpb[y][x]+1+c[y+1][x] {
dpb[y+1][x] = dpb[y][x] + 1 + c[y+1][x]
q = append(q, [3]int{y + 1, x, 1})
}
}
if x != 0 {
if dpb[y][x-1] > dpb[y][x]+1+c[y][x-1] {
dpb[y][x-1] = dpb[y][x] + 1 + c[y][x-1]
q = append(q, [3]int{y, x - 1, 1})
}
}
if x != N-1 {
if dpb[y][x+1] > dpb[y][x]+1+c[y][x+1] {
dpb[y][x+1] = dpb[y][x] + 1 + c[y][x+1]
q = append(q, [3]int{y, x + 1, 1})
}
}
}
}
println(min(dpa[N-1][N-1], dpb[N-1][N-1]))
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Recommended Posts