問題一覧 > 通常問題

No.3704 Awkward Pairs

レベル : / AI推定難易度 : 450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 36
作問者 : Rapca1256 / テスター : tomorunn
お気に入りにしたユーザー ProblemId : 13990 / 自分の提出
問題文最終更新日: 2026-09-10 17:29:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
JOI1次風非公式模試 (Suken Programming Contest 007) (順位表) の他の問題:

Problem Statement

$2N$ people of various ages attended a party hosted by the mean-spirited Suken. The $i$-th participant is numbered $i$ and is $A_i$ years old.
The $2N$ people are now to be divided into a total of $N$ pairs of $2$ people each. Here, the awkwardness of a pair is the absolute value of the difference between the ages of its $2$ people. Find the maximum possible value of the sum of the awkwardness over all pairs. Also, output one example of such a pairing. See Output for the output format.

Input

$N$
$A_1\ A_2\ \cdots\ A_{2N}$

Constraints

  • $1 \le N \le 2\times 10^5$.
  • $1 \le A_i \le 10^9$.
  • All inputs are integers.

Partial Score

This problem has partial scoring based on subtasks.

SubtaskScoreConstraints
小課題140% (60 pts)$i=1,2,\cdots, 2N-1$ について, $A_i \le A_{i+1}$
小課題260% (90 pts)追加の制約はない.

Output

Output $N+1$ lines. On line $1$, output the maximum awkwardness, and on line $i+1$, output the numbers of the people in the $i$-th pair, separated by a space.
Any output satisfying the conditions will be judged as correct.
Do not output anything other than the answer. (Do not output text such as prompts for input either.)

Sample

Sample 1
Input
3
1 3 4 5 6 8
Output
11
1 6
4 3
2 5

Other outputs, such as $(5, 2), (1, 6), (3, 4)$, are also correct.
This sample input satisfies the constraints of all subtasks.

Sample 2
Input
1
1 1
Output
0
1 2

This sample input satisfies the constraints of all subtasks.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。