社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：

输入第一行给出一个正整数N（2≤N≤105）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。

输出格式：

按下列格式输出：

Outgoing #: N1
Introverted #: N2
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing #: 5
Introverted #: 5
Diff = 3611

输入样例2：

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

Outgoing #: 7
Introverted #: 6
Diff = 9359

代码长度限制

16 KB

时间限制

150 ms

内存限制

64 MB

栈限制

8192 KB

import java.util.*;
import java.io.*;

/**
 * 【L2-017 人以群分】
 * 1. 快速选择 将平均复杂度控制在 O(N)，仅对关心的区间进行划分。
 * 2. 内联 将 swap 和分区逻辑直接写在 main 函数循环内，省去函数调用开销。
 * 3. 霍尔分区 相比 Lomuto 方案，数据交换频率更低，处理重复元素更稳健。
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Reader fr = new Reader();
        int n = fr.nextInt();
        if (n <= 0) return;
        
        int[] v = new int[n];
        long totalSum = 0; // 总和可能突破 2^31-1，必须使用 long
        for (int i = 0; i < n; i++) {
            v[i] = fr.nextInt();
            totalSum += v[i];
        }

        // 2. 目标规模：k 为内向型人数（取 N/2 保证两组最接近）
        int k = n / 2;
        
        // 3. 迭代版快速选择：原地调整数组 v，使前 k 个元素为全局最小
        int left = 0, right = n - 1;
        while (left <= right) {
            if (left == right) break;
            
            // 选取左、中、右三个位置的中位数并置于 mid，防止数组近乎有序时退化至 O(N^2)
            int mid = (left + right) >>> 1;
            if (v[left] > v[mid]) { int t = v[left]; v[left] = v[mid]; v[mid] = t; }
            if (v[left] > v[right]) { int t = v[left]; v[left] = v[right]; v[right] = t; }
            if (v[mid] > v[right]) { int t = v[mid]; v[mid] = v[right]; v[right] = t; }
            
            int pivot = v[mid];
            int i = left, j = right;
            
            // 【核心：Hoare 双指针对撞分区】
            // i, j 指针从两侧对撞，遇到失序元素即交换
            while (i <= j) {
                while (v[i] < pivot) i++; // 寻找左侧不应存在的“大值”
                while (v[j] > pivot) j--; // 寻找右侧不应存在的“小值”
                if (i <= j) {
                    // 内联交换逻辑
                    int t = v[i]; v[i] = v[j]; v[j] = t;
                    i++;
                    j--;
                }
            }
            
            // 【区间剪枝】
            // 判断第 k 小的数在哪一侧，只处理有意义的区间
            if (k <= j) {
                right = j;
            } else if (i <= k) {
                left = i;
            } else {
                break; // k 恰好就在 pivot 位置
            }
        }

        // 
        
        // 4. 计算最小 k 个人的活跃度总和
        long sumSmall = 0;
        for (int i = 0; i < k; i++) sumSmall += v[i];

        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        out.println("Outgoing #: " + (n - k));
        out.println("Introverted #: " + k);
        // 公式：Diff = (TotalSum - sumSmall) - sumSmall
        out.println("Diff = " + (totalSum - 2 * sumSmall));
        out.flush();
        out.close();
    }

    /**
     * 高性能字节读取器：
     * 直接读取字节数组进行 ASCII 转换
     */
    static class Reader {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16]; // 64KB 缓冲区
        private int ptr = 0, len = 0;

        private int read() throws Exception {
            if (ptr == len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buf[ptr++];
        }

        public int nextInt() throws Exception {
            int c = read();
            while (c >= 0 && c <= 32) c = read(); // 过滤空格、换行
            int res = 0;
            while (c >= '0' && c <= '9') {
                res = res * 10 + (c - '0');
                c = read();
            }
            return res;
        }
    }
}