ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6221
サブタスク

자동 정렬 시스템 1s 1024MB

問題

정올이는 N개의 정수 A_1, A_2, ..., A_N을 정렬하기 위해 반복적으로 배열 A에서 가장 작은 정수를 찾아 제거하고 이를 배열 B의 끝에 추가한다.

정올이는 M개의 정수 중 가장 작은 수를 찾기 위해 M초의 시간이 걸리는데, 정렬을 빠르게 하기 위해 이번에 새로 구매한 로봇의 도움을 받아 자동 정렬 시스템을 구축하려한다.

로봇은 정수 x를 삽입하면 x초 후에 해당 수를 수열 B에 추가하는데, 정올이는 로봇에게 원하는 만큼의 정수를 주어 빠르게 정렬을 진행할 계획이다. (만약 로봇과 정올이가 동시에 정수를 추가하려 한다면 정올이가 우선적으로 처리된다)

정올이가 로봇을 최대한 효율적으로 사용하였을 때, 정렬에 걸리는 최소 시간을 알아보자.


入力

첫 줄에는 독립적인 테스트 케이스의 수 T가 주어진다 (1 \le T \le 10).

각 테스트 케이스는 다음과 같이 구성된다:

  • 각 테스트 케이스의 첫 번째 줄에는 정올이의 배열에 있는 정수의 수 N이 주어진다. (1 \le N \le 2 \cdot 10^5)

  • 다음 줄에는 정올이가 정렬해야 할 정수 A_1, A_2, \dots, A_N이 주어진다. 동일한 정수가 여러 번 등장할 수 있다. (1 \le A_i \le 10^{11}; 1 \le i \le N)

모든 테스트 케이스의 N의 합은 2 \cdot 10^5를 넘지 않는다.


出力

각 테스트 케이스에 대해 정올이가 정수들을 최적으로 나누었을 때 정렬에 걸리는 최소 시간을 새로운 줄에 출력하라.


部分問題

番号 点数 条件
#125点

N≤16

#225点

N≤150

#325点

∑N≤5000

#425点

추가 제약 조건 없음


例題 

2
8
4 3 3 1 8 2 7 10
3
10 100 1000
10
6

첫 번째 테스트 케이스는 아래와 같은 시간 순서로 진행된다.

두 번째 테스트 케이스는 로봇을 이용하지 않는 것이 최선이다.



出典

USACO 2024 January Gold

ログインしないとコードを書けません。