分组对话

[编程题]分组对话

热度指数：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)

牛客562496337号

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int fun(priority_queue<int,vector<int>,less<int>> pq){
if(pq.size()<3)
  return 0;
int ret=0;
while(pq.size()>2){
  int first= pq.top();
  pq.pop();
  int second= pq.top();
  pq.pop();
  int third= pq.top();
  pq.pop();
  if(--first>0)
   pq.push(first);
  if(--second>0)
   pq.push(second);
  if(--third>0)
   pq.push(third);
  ret++;
}
return ret;
}
int main(){
int n;
cin>>n;
while(n--){
  int c;
  cin>>c;
  priority_queue<int,vector<int>,less<int>> pq;
  while(c--){
   int a;
   cin>>a;
   if(a>0)
    pq.push(a);
  }
  int ret=fun(pq);
  cout<<ret<<endl;

}

return 0;

}

发表于 2020-09-01 18:14:41 回复(0)

牛客764442872号

大家帮我看看哪里错了呢？通过率百分之0？

import heapq
c = int(input())
ans = []
for i in range(c):
    istr = input()
    nums = list(map(int, istr.split()))
    num = [-x for x in nums[1:] if x>0]
    #print (num)
    heapq.heapify(num)
    #print (num)
    count = 0
    
    while (len(num)>2):
        tmp = []
        for j in range(3):
            tmpi = heapq.heappop(num)
            if -tmpi>1:
                tmp.append(tmpi+1)
        count += 1
        for tmpi in tmp:
            heapq.heappush(num, tmpi)
    print (count)

发表于 2020-08-02 01:01:27 回复(0)

何时能像老胡这么优秀？

import sys
 
 
def solution(nums):
    count = 0
    while len(nums) > 2:
        nums.sort(reverse=True)
        count += nums[2]
        c1 = nums[0]-nums[2]
        c2 = nums[0]-nums[1]
        nums = nums[3:]
        if c1 > 0: nums.append(c1)
        if c2 > 0: nums.append(c2)
    return count
 
 
if __name__ == '__main__':
    c = int(sys.stdin.readline().strip())
    while c > 0:
        line = [int(data.strip()) for data in sys.stdin.readline().split()]
        # assert len(line[1:]) == line[0]
        nums = [data for data in line[1:] if data > 0]
        print(solution(nums))
        c -= 1

断言有问题？

发表于 2020-07-30 17:23:03 回复(2)