分组对话_牛客博客

猿辅导课堂上老师提供了一些角色，学生可以从中选择一个自己喜欢的角色扮演，每3个不同的角色就可以组成一个小组，进行分组对话。
当老师点击开始分组对话按钮的时候，服务器会为已经选择自己角色的同学分配对话小组，请问最多能组成多少个对话小组？

输入描述:
第一行为测试用例数量C(C<=100)，接下来的C行每行为一个测试用例
每个用例的第一个数字表示可供选择的角色数量T(T<=1000)，接下来的T个数字表示每个角色的选择人数Pi(Pi<=500)

输出描述:
一共C行，每行表示一个测试用例中的最大对话小组数量。

用贪心算法来考虑如何分配小组：每次都选人数最多的三个角色来分组
用大根堆或者java自带的优先队列可以在 $O(logT)$ 的时间复杂度内找出最大的三个数

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner input;
        int C, T, i, j;
        int[][] P;

        input = new Scanner(System.in);
        C = input.nextInt();
        P = new int[C][];
        for(i = 0; i < C; i++){
            T = input.nextInt();
            P[i] = new int[T];
            for(j = 0; j < T; j++){
                P[i][j] = input.nextInt();
            }
        }
        for(i = 0; i < C; i++){
            System.out.println(Solution(P[i]));
        }
        input.close();
    }

    private static int Solution(int[] P){
        int first, second, third, ans;
        PriorityQueue<Integer> pq;

        ans = 0;
        pq = new PriorityQueue<>((a, b) -> b - a);
        for(int p : P){
            if(p > 0){
                pq.offer(p);
            }
        }
        while(pq.size() > 2){
            first = pq.poll();
            second = pq.poll();
            third = pq.poll();
            if(--first > 0){
                pq.offer(first);
            }
            if(--second > 0){
                pq.offer(second);
            }
            if(--third > 0){
                pq.offer(third);
            }
            ans++;
        }
        return ans;
    }
}