贪心算法训练 运动员分组

Ⅰ 题目 运动员分组

有N个人参加100米短跑比赛。跑道为8条。程序的任务是按照尽量使每组的人数相差最少的原则分组。
例如: 
N=8时,分成1组即可。 
N=9时,分成2组:一组5人,一组4人。 
N=25时,分4组:7、6、6、6。  
请编程计算分组数字。 
要求从标准输入获得一个正整数(1~100之间,不必考虑输入错误的情况),表示参赛的人数。 
程序输出每个组的人数。从大到小顺序输出,每个数字一行。 

比如, 
用户输入:25 
程序输出: 
7 
6 
6 
6

Ⅱ 整体的思路

① 输入人数N;② 判断分组的数目;③ 根据分组每次向组中添加一个人(贪心)

Ⅲ 部分代码

1
2
3
4
5
6
7
8
9
10
11
12
private static void greedGroup(int[] arr, int N,int gNum) {
//整数部分
int t = N/gNum;
for(int i = 0; i < arr.length; i++)
arr[i] = t;
//剩余的部分(从后往前所以要减一)
t = N%gNum - 1;
while(t >= 0){
arr[t] += 1;
t --;
}
}

Ⅳ 全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;
public class Group {
private static Scanner sc;
public static void main(String[] args) {
sc = new Scanner(System.in);
int N = sc.nextInt();//输入人数 N
int gNum = (N/8+1)%8;//确定分几个组,这个位置要记得加一
int arr[] = new int[gNum];//将最后的结果保存在数组中并且遍历数组
greedGroup(arr,N,gNum);
traverse(arr);//遍历输出
}
private static void traverse(int[] arr) {
for(int x:arr){
System.out.println(x);
}
}
/**
* 贪心核心
* */
private static void greedGroup(int[] arr, int N,int gNum) {
//整数部分
int t = N/gNum;
for(int i = 0; i < arr.length; i++)
arr[i] = t;
//剩余的部分(从后往前所以要减一)
t = N%gNum - 1;
while(t >= 0){
arr[t] += 1;
t --;
}
}
}