首页 > 试题广场 >

分组对话

[编程题]分组对话
  • 热度指数：1039 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
猿辅导课堂上老师提供了一些角色，学生可以从中选择一个自己喜欢的角色扮演，每3个不同的角色就可以组成一个小组，进行分组对话。
当老师点击开始分组对话按钮的时候，服务器会为已经选择自己角色的同学分配对话小组，请问最多能组成多少个对话小组？

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

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


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

输入

3
3 1 1 1 
3 2 2 3
4 0 2 3 99

输出

1
2
2

说明

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

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

对于用例3，学生扎堆选择了最后一个角色，但是第二个角色只有2个人，所以还是只能构成2个对话小组。
算法知识视频讲解
添加回答
那天灯下的我头像 那天灯下的我
最好想的办法，对输入的数组进行排序，判断剩余的可选的是否还大于3个，把最少的一种角色和最多的两种角色的数量减一，再排序，以此循环，直到剩余的可选角色数量不足三个。时间复杂度爆炸，然而竟然能过 
import java.util.*;
public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num ; i++) {
            int length = scanner.nextInt();
            int[] array = new int[length];
            for (int j = 0; j< length; j++) {
                array[j] = scanner.nextInt();
            }

            cal(array);

        }
    }
    public static void cal(int[] array){
        int num = 0;
        while (true) {
            Arrays.sort(array);
            int i ;
            for (i = 0; i<array.length;i++){
                if (array[i] == 0)
                    continue;
                else
                    break;
            }
            if (i>array.length-3){
                break;
            }
            else {
                array[i] -= 1;
                array[array.length-1] -= 1;
                array[array.length-2] -= 1;
                num++;
            }
        }
        System.out.println(num);
    }
}


发表于 2020-08-01 14:58:16 回复(5)
牛客745599318号头像 牛客745599318号 
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int main(){
	int C;
	cin>>C;
	while(C--){
		int n;
		cin>>n;
		priority_queue<int, vector<int>, less<int>> que;
		for(int i=0;i<n;i++){
			int t;cin>>t;
			que.push(t);
		}
		int ans = 0;
		while(que.size()>=3){
			int a= que.top();que.pop();
			int b= que.top();que.pop();
			int c= que.top();que.pop();
			int d = c;
			if(!que.empty()){
				d = c - que.top() + 1;
			}
			ans += d;
			if(a>d) que.push(a-d);
			if(b>d) que.push(b-d);
			if(c>d) que.push(c-d);
		}
		cout<<ans<<endl;
	}
	return 0;
}

发表于 2020-07-28 16:54:06 回复(4)
黎明之墟头像 黎明之墟
开始做的时候直接挑三个最大的减去其中最小的再放回去两个，过不了，后来想了一下可能会造成浪费的情况
比如3 3 3 3按上面的思路一次之后变成3 0 0 0，三组
但是如果减到每次挑最大的三个-1，就会是3 2 2 2 -> 2 2 1 1 ->1 1 1 0->0 0 0 0，四组
加速的话就是挑三个最大的，把其中最小的减到和第四大的一样，这种方法代码有很多大佬写了，就不贴了

根据上面分析的，其实就是看最大的两个数和其他数之间的和的关系，加入共有n个数，如果前n-2个数大于第n-1个数 那么来回相减肯定能消成只剩1个2个的情况，第n-1个数的关系同理，代码如下，牛客的测试用例都过了，有问题欢迎指正 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int count = sc.nextInt();

        while(count > 0){
            int num = sc.nextInt();
            int[] arr = new int[num];
            int sum = 0;
            int rs = 0;
            
            for(int i=0; i<num; i++){
                arr[i] = sc.nextInt();
                sum += arr[i];
            }

            if(num >= 3){
                Arrays.sort(arr);
                if(sum - arr[num - 1] - arr[num - 2] <= arr[num - 2]){//前n-2个数一起最多能把n-2减完
                    rs = sum - arr[num - 1] - arr[num - 2];
                }else if(sum - arr[num - 1] <= arr[num - 1]){//前n-1个数一起最多能把n-1减完
                    rs = (sum - arr[num - 1]) / 2;
                }else {
                    rs = sum / 3;
                }
            }

            System.out.println(rs);
            --count;
        }
    }
}




编辑于 2020-08-01 19:22:22 回复(0)
华科菜菜子头像 华科菜菜子 
//利用最大堆保持最大的三个数值变化后的序列
//每次sum+上第3大的值减去第4大的值+1，得到比第三大的值小的一个值
//如果剩余不为0的数值小于等于3，则加上最小值
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
    int n;cin>>n;
    while (n--)
    {
            int m;
            cin >> m;
            priority_queue<int,vector<int>,less<int>> p;
            for (int j = 0; j < m; j++)
            {
                int temp;
                cin >> temp;p.push(temp);
            }
            int sum = 0; 
            while (p.size() >= 3)
            {
                    int a = p.top(); p.pop();
                    int b = p.top(); p.pop();
                    int c = p.top(); p.pop();
                    int d = c;
                    if(!p.empty())
                        d = c - p.top() + 1;
                    sum += d;
                    if (a>d)
                        p.push(a-d);
                    if (b>d)
                        p.push(b-d);
                    if (c>d)
                        p.push(c-d);
            }
            cout<<sum<<endl;
    }
    return 0;
}

发表于 2020-12-22 08:51:38 回复(0)
李栋吧头像 李栋吧
使用大顶堆来存储T个数据。注意java中的PriorityQueue默认是小顶堆，需要进行翻转处理，如下 
            Queue<Integer> heap = new PriorityQueue<>((o1,o2)->Integer.compare(o2,o1));

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //第一行为测试用例数量C
        //每个用例的第一个数字表示可供选择的角色数量T(T<=1000)，接下来的T个数字表示每个角色的选择人数Pi(Pi<=500)
        int C = sc.nextInt();
        while(C-- > 0){
            int T = sc.nextInt();
            //用大顶堆来存储T个数据
          // Queue<Integer> heap = new PriorityQueue<>();
            Queue<Integer> heap = new PriorityQueue<>((o1,o2)->Integer.compare(o2,o1));
            for(int i = 0;i < T;i++){
               int p = sc.nextInt();
               heap.add(p);
            }
            int res = 0;
            while(heap.size()>=3){
                int a = heap.peek();
                heap.poll();
                int b = heap.peek(); 
                heap.poll();
                int c = heap.peek(); 
                heap.poll();
                int d = c;
                if(!heap.isEmpty()){
                    d = c - heap.peek() + 1;
                }
                ans += d;
                if(a > d) heap.add(a-d);
                if(b > d) heap.add(b-d);
                if(c > d) heap.add(c-d);              
            }
            System.out.println(res); 
        }
        
        
    }
}
编辑于 2020-08-01 15:31:50 回复(0)
zjuiuczy头像 zjuiuczy
4 0 2 3 99 这一个测试跑出来的结果是3 都能过？
是不是应该加一个>0才push的条件
发表于 2020-08-01 07:00:27 回复(0)
牛客738797044号头像 牛客738797044号
#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

void add(vector<int>& v, int t) {
    if (t <= 0)
        return;
    v.push_back(t);
    for (int i = v.size() - 1; i >= 1; --i)
        if (v[i] < v[i - 1]) {
            int tem = v[i];
            v[i] = v[i - 1];
            v[i - 1] = tem;
        }
    return;
}

int main() {
    int N;
    cin >> N;
    //vector<int> ans;
    while (N--) {
        int m;
        cin >> m;
        vector<int> res;
        while (m--) {
            int t;
            cin >> t;
            add(res, t);
        }
        int count = 0;
        while (res.size() >= 3) {
            int c = res.back();
            res.pop_back();
            int b = res.back();
            res.pop_back();
            int a = res.back();
            res.pop_back();
            int d=1;
            if(!res.empty())
                d=a-res.back()+1;
            count+=d;
            add(res, c - d);
            add(res, b - d);
            add(res, a - d);
        }
        cout<<count<<endl;
    }
    return 0;
}
发表于 2020-07-28 11:01:48 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 猿辅导 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
7条回答 2716浏览

热门推荐

通过挑战的用户

相关试题

分组对话

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号