https://www.acmicpc.net/problem/2786
b를 기준으로 오름차순 정렬한 다음에 부분합 계산 해놓고
● b에서 [0, i-2] 구간을 더한 값과 [i-1, n-1] 구간에서 가장 작은 a값 더하기
● [0, i-1] 구간 중 가장 작은 a를 가진 인덱스를 찾음. 이걸 j라고 하면 [0, i-1] 구간 합에서 b[j]를 빼고 a[j]를 더함.
이 두가지 방법 중 더 작은것을 출력하면 될 거 같음
이런 식으로 하면 특정 구간에서 가장 작은 a를 찾아야 하는데
seg tree를 쓰면 될 것 같음
근데 다른사람들 제출한거 보면 코드 길이가 짧더라고
내가 생각한 방법으로 하면 엄청 길텐데
다른 방법이 있나
근데 왜 물음표 쓰면 글이 안써지냐 짜증나게
구간 형태를 잘 보셈. 세그트리가 정말로 필요함?
아 priority queue 쓰면 되나?
이 댓글은 게시물 작성자가 삭제하였습니다.
그냥 소팅해놓고 인덱스만 하나씩 옮기면서 더해도 되는거 아니냐
그리고 풀이가 잘못된부분이 있음
왜 답글 두개달리냐 짜증나네
생각좀 다시 해봐야겠다
아 두번째 방법에서 가장 작은 a를 고르는게 아니라 a하고 b의 차가 제일 작은걸 골라야 하겠네
풀이가 이상한데...
접근이 조금 이상한 것 같음
아 모르겠다 걍 풀이 볼까
와 답글기능 생겼네?
엄청 어렵지 않은거같은데 푼사람 왜이렇게 적지