codeforces 478B Random Teams 解题报告

题目链接：http://codeforces.com/problemset/problem/478/B

题目意思：有 n 个人，需要将这班人分成 m 个组，每个组至少含有一个人，同一个组里的人两两可以结交成一个pair，问怎样分配，可以使得 pair 数最少和最多，输出之。

首先最多 pair 数是很容易求出的，就是 m-1 个组里都放 1 个人，然后最后那个组（即第 m组）人数最多，pair数自然最多，答案就是 (n-m+1) * (n-m) / 2。

最少 pair 数，做的时候有一点点思路：就是使得尽可能多的组的人数尽量平均。好像事实证明是正确的，不过最终表达式....改了 n 次都无果，最后大数据卡住无从下手，又做了些无节操的事～～～学会就好，学会就好，呵呵呵～～～。

61ms 4KB

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef __int64 LL;
 9 
10 inline LL get_pair(LL tmp)
11 {
12     return (tmp * (tmp-1)) >> 1;
13 }
14 
15 int main()
16 {
17     LL m, n;
18     while (scanf("%I64d%I64d", &n, &m) != EOF)
19     {
20             LL k = n / m, tk = k + 1;
21             LL r = n % m, l = m - r;     // 这四条式子请大家好好体会
22             LL minans = r * get_pair(tk) + l * get_pair(k);
23 
24             LL maxremain = n - (m-1);
25             LL maxans = get_pair(maxremain);
26 
27             printf("%I64d %I64d
", minans, maxans);
28     }
29     return 0;
30 }

加了些特判，一下子15ms 0KB 了