CF82D Two out of Three

Vasya 最近设计了一种新算法来优化客户流的接待，他考虑了如下问题。 现有一个共有 $n$ 个人的收银台队列，每个人都有一个正整数 $a_{i}$，表示为该客户服务所需的时间。这个收银台的特殊之处在于它可以同时为两个客户服务。然而，如果两位客户分别需要 $a_{i}$ 和 $a_{j}$ 的服务时间，同时为两人服务所需的总时间为 $max(a_{i}, a_{j})$。请注意，客户的服务过程是不可中断的，因此，如果两个客户同时到收银台，他们会同时开始服务，并且同时结束服务（也就是说较快的那个人要等待较慢的那个人）。 Vasya 在他的算法中采用了巧妙的启发式方法——只要队列中还有超过一个人等待，就从队首的前三个人中选择两个人一起服务。如果队列中只剩下一个客户编号 $i$，那么他单独接受服务，所用时间为 $a_{i}$。请注意，总共需要服务的阶段数始终为 $⌈n/2⌉$。 Vasya 认为这种方法有助于缓解我们都讨厌的排队。因此，他希望你设计一个程序，确定采用这种算法后，处理完整个队列所需的最短时间。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示队列中人数。第二行包含 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^6$），以空格分隔。队首编号为 $1$。

输出一行，表示处理所有 $n$ 个人所需的最短时间。接下来输出 $⌈n/2⌉$ 行，按阶段给出每次同时服务的客户编号。每行为本阶段同时接受服务的两个人的编号，中间用空格隔开；若 $n$ 为奇数，最后一行只输出单独接受服务的客户编号。编号从 $1$ 开始。

由 ChatGPT 5 翻译