分组对话

[编程题]分组对话

热度指数：808 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

猿辅导课堂上老师提供了一些角色，学生可以从中选择一个自己喜欢的角色扮演，每3个不同的角色就可以组成一个小组，进行分组对话。

当老师点击开始分组对话按钮的时候，服务器会为已经选择自己角色的同学分配对话小组，请问最多能组成多少个对话小组？

输入描述:

第一行为测试用例数量C(C<=100)，接下来的C行每行为一个测试用例

每个用例的第一个数字表示可供选择的角色数量T(T<=1000)，接下来的T个数字表示每个角色的选择人数Pi(Pi<=500)

输出描述:

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

示例1

输入

输出

1
2
2

说明

对于用例1，正好3个不同角色，每个角色1个人选，于是构成且只能构成一个小组。

对于用例2，在构成两个小组之后，第3个角色单了1人无法构成任何小组，所以最大小组数量是2。

对于用例3，学生扎堆选择了最后一个角色，但是第二个角色只有2个人，所以还是只能构成2个对话小组。

算法知识视频讲解

Java

1+½+¼+⅛+...

//贪心算法+优先队列/堆
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;
    }
}

发表于 2019-12-23 16:19:08 回复(0)