猿辅导课堂上老师提供了一些角色,学生可以从中选择一个自己喜欢的角色扮演,每3个不同的角色就可以组成一个小组,进行分组对话。
当老师点击开始分组对话按钮的时候,服务器会为已经选择自己角色的同学分配对话小组,请问最多能组成多少个对话小组?
第一行为测试用例数量C(C<=100),接下来的C行每行为一个测试用例
每个用例的第一个数字表示可供选择的角色数量T(T<=1000),接下来的T个数字表示每个角色的选择人数Pi(Pi<=500)
一共C行,每行表示一个测试用例中的最大对话小组数量。
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个对话小组。
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); } }
#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; }
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; } } }
//利用最大堆保持最大的三个数值变化后的序列 //每次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; }
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); } } }