28031 Milk Sum

Link to original note: 2023-10-26 목

10:34:07

종이에 생각중

10:40:31

문제 요약

${A_{i}}$ 가 있을 때 적당한 순서로 배열해서

$$S = \sum_{i=1}^{n}{i*A_{i}}$$
를 maximize 해야 한다.

이제 $Q$개의 쿼리가 들어온다.

쿼리 $i ; j$는 $A_i$를 $j$로 바꿨을 때, $S$의 최댓값을 구하고, $A_i$를 원상복구 시키는 것이다.

문제 풀이

당연히, 그리디 하게
${A_{i}}$ 를 단조 증가하도록 바꾼 ${B_{i}}$ 를 관리하면 된다.

${B_{i}}$ 에서 최댓값이 나오기 때문이다.

편의 상 $B_{0}=-\infty, B_{n+1} = \infty$ 로 두자.

$id_{i}$를 $A_{i}$의 $B_i$에서의 인덱스라 하자. 즉 $B_{id_{i}} = A_{i}$

$A_i$를 $j$로 바꿨을 때 $B_i$에서의 $lower_bound$ 인덱스를 $k$라 해보자.

$S \quad -= id_{i} \cdot B_{id_{i}}$
은 모든 케이스에서 진행된다.

Case 1: $k \lt id_{i}$

$[B_{k}, B_{id_{i}-1}]$ 의 합만큼 $S$에 더해진다…
$S \quad += k \cdot j$

Case 2: $k \gt id_{i}$

$[B_{id_{i}+1}, B_{k-1}]$ 의 합만큼 $S$에서 빼진다
$S \quad += (k-1) \cdot j$

Case 3: $k = id_i$

$S \quad += k \cdot j$

11:06:30

생각보다도 훨씬 Mathjax가 비효율적이다.

구현

Python bisect로 진행.

11:26:47

1차 코드 제출 -> 틀렸습니다.

알고보니 Case 3이 잘못됐었음. 위에 공통 사항 고치다가 추가를 안해줌.

2차 코드 제출 -> 틀렸습니다. 45%

가장 작은 원소를 0이 아니라 $-1$로 뒀어야 한다. (구간합에는 영향 X)

11:32:26

난이도 평가 완료. 끝.
.
.
.
이 글은 [Daily] Vault에서 작성되었습니다.