济南做门户网站开发公司,张家界旅游,番禺网站开发,wordpress 手机 跳转目录
题目描述
输入格式#xff1a;
输出格式#xff1a;
输入样例 1#xff1a;
输出样例 1#xff1a;
输入样例 2#xff1a;
输出样例 2#xff1a; 题解#xff1a; 题目描述
学校新建了宿舍楼#xff0c;共有 n 间寝室。等待分配的学生中#xff0c;有女…目录
题目描述
输入格式
输出格式
输入样例 1
输出样例 1
输入样例 2
输出样例 2 题解 题目描述
学校新建了宿舍楼共有 n 间寝室。等待分配的学生中有女生 n0 位、男生 n1 位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去最后不能有寝室留空。 现请你写程序完成寝室的自动分配。分配规则如下
男女生不能混住不允许单人住一间寝室对每种性别的学生每间寝室入住的人数都必须相同例如不能出现一部分寝室住 2 位女生一部分寝室住 3 位女生的情况。但女生寝室都是 2 人一间男生寝室都是 3 人一间则是允许的在有多种分配方案满足前面三项要求的情况下要求两种性别每间寝室入住的人数差最小。
输入格式
输入在一行中给出 3 个正整数 n0、n1、n分别对应女生人数、男生人数、寝室数。数字间以空格分隔均不超过 105。
输出格式
在一行中顺序输出女生和男生被分配的寝室数量其间以 1 个空格分隔。行首尾不得有多余空格。 如果有解题目保证解是唯一的。如果无解则在一行中输出 No Solution。
输入样例 1
24 60 10输出样例 1
4 6注意输出的方案对应女生都是 24/46 人间、男生都是 60/610 人间人数差为 4。满足前三项要求的分配方案还有两种即女生 6 间都是 4 人间、男生 4 间都是 15 人间或女生 8 间都是 3 人间、男生 2 间都是 30 人间。但因为人数差都大于 4 而不被采用。
输入样例 2
29 30 10输出样例 2
No Solution 题解
import java.util.*;public class Main {static class Pair {int a, b, mx;}public static void main(String[] args) {Scanner sc new Scanner(System.in);int N 100010;Pair[] s new Pair[N];int n0 sc.nextInt(), n1 sc.nextInt(), n sc.nextInt();int flag 1, kk 0;for (int i n-1; i1; i --) {int j n - i;if (n0 % i 0 n1 % j 0) {if (n0/i 1) continue;if (n1/j 1) continue;flag0;s[kk]new Pair();s[kk].a i;s[kk].b j;s[kk].mx Math.abs(n0 / i - n1 / j);kk;}}Arrays.sort(s, 0, kk, new ComparatorPair() {public int compare(Pair aa, Pair bb) {return aa.mx - bb.mx;}});if (flag 1)System.out.println(No Solution);elseSystem.out.println(s[0].a s[0].b);}
}
