A25179. 零食好友
填空题
容易
知识点
题目描述
零食好友
题目描述：
有 n 个小朋友去参加户外野餐活动，他们被分成了 m 个小组，保证每个小组至少有一个小朋友。
在野餐过程中，同一小组内的任意两个小朋友都会互相分享零食，成为一对“零食好友”。
你的任务是编写一个程序，请计算对于不同的分组方案，每种方案中的所有小组的“零食好友”的对数之和，并输出其中最小值和最大值分别是多少。
例如：n = 4，m = 2；4 个小朋友被分为 2 个小组。共有两种分组方案：
（1）第一组 1 人，第二组 3 人，则第一组有 0 对“零食好友”，第二组有 3 对“零食好友”，共有 3 对“零食好友”；
（2）第一组 2 人，第二组 2 人，则第一组有 1 对“零食好友”，第二组有 1 对“零食好友”，共有 2 对“零食好友”。
则所有分组方案中，“零食好友”的对数之和的最小值是 2，最大值是 3。
输入描述：
本题的每个测试点都有多组测试数据，格式如下：
第一行输入一个整数 T（1≤T≤100），表示数据组数；
接下来 T 组数据，每组数据输入仅一行，包含两个整数 n 和 m（1≤m≤n≤10^9），分别表示该组数据中小朋友的数量以及分组数量，整数之间以一个空格隔开。
输出描述：
共 T 行，每行输出两个整数，表示对应的测试数据中“零食好友”对数的最小值和最大值，整数之间以一个空格隔开。
样例输入：
2
4 2
8 5样例输出：
2 3
3 6参考答案
#include <iostream>
using namespace std;
int main() {
int t, n, m;
cin >> t;
for(int i=0; i<t; i++) {
cin >> n >> m;
//最大值，尽可能多的人集中在一个小组
//即前面m-1组人数为1，最后一个小组人数为n-m，最大值是最后一组的组合数
int min = (n - m + 1) * (n - m) / 2;
//最小值，每个小组的人数平均分布
//每组q+1人，共r组；每组q人，共m-r组
int q = n/m;
int r = n % m;
int max = r * q * (q+1) / 2 + (m-r) * q * (q - 1) / 2;
cout << max << " " << min << endl;
}
return 0;
}
上一题
下一题