重庆师范大学第一届ACM选拔赛（公开赛）G-团日活动

一、G-团日活动

题目描述
华华和班里的同学共N人一起去校外进行团日活动。到了晚上回家的时候，遇到一处独木桥要过，为了安全起见，华华提议一次只让两名同学过独木桥，
已知队伍中n名女生过桥都比较快，单独过桥只需要1分钟。m名男生因为体重较重，过桥的时间比较慢，
每名男生单独沟过桥分别需要1,2,3,4……分钟的时间来过桥。
当两个人同时过桥时，他们的过桥时间为较慢的那一名同学所需要的时间。
问，所有同学都过完独木桥所需要的最短时间是多少。

输入描述:
多组输入，第一行输入数据组的数目T（T<=1000）
第二行输入团队总人数N，和男生的人数n
(N<=1e9,m<N,n<N,数据保证团队中至少有1名男生或者1名女生）

输出描述:
每一行输出所有人过桥所需要的最短总时间。

示例1
输入

4
10
5
20
16
31
15
41
20

输出

11
74
72
121

示例2
输入

1
1000000000
999999998

输出

249999999500000001

二、解题思路：

读完题后，根据蓝色字体的两句话可知道解题的大致思路：

2.1思路

男生m个人的各过桥时间是1~m依次递增的，且两个人过桥时间取长的那段，所以两人过桥时应优先选择两个过桥时间最长的男生。
女生过桥都是1分钟，所以也应两两一队过桥。

2.2考虑奇偶

此时再考虑各自人数奇偶之分，例如若男生人数是奇数，则必定剩下一个过桥时间最短的（1min），可以有两个思路：
①将1min男生移去女生队伍，当成男生-1&&女生+1
②将一个女生移入男生队伍配对，男生+1&&女生-1（推荐）

2.2.1奇偶情况举例说明

下面举四种奇偶情况作为说明：

tip：min_t表示最短时间，算式中蓝色为男生时间，橘色为女生时间。

1. 女生人数n偶，男生人数m偶
   m = 4 ： :1 2 3 4
   n= 2： 1 1
   min_t = 4+2+ 2/2=7
   （男生中两两配对，则应4、3一队，min_t+=4， 2、1一队，min_t+=2；
   女生亦两两配对，直接用人数/2即可。）

2. 女生人数n奇，男生人数m奇
   m = 5：1 2 3 4 5
   n = 7 ：1 1 1 1 1 1 1
   min_t = 1+5+3+ +7/2=12
   (男生：5、4一队，3、2一队，剩1，这时可假设将一个女生移入男生队列配对，一男一女过桥时间为1，男生时间算式就可为5+3+1；,
   int除法向下取整，故移走一个女生后，女生时间仍为7/2=3)

3. 女生人数n偶，男生人数m奇
   m = 5： 1 2 3 4 5
   n =4 ： 1 1 1 1
   min_t = 1+5+3+ +4/2= 11
   （男生情况跟第二种一样，剩一个1min男生，移入一个女生后男生时间为5+3+1；
   此时女生人数变为奇数3，两两配对的话会剩一个女生，需要一个人单独走（题目并没有说这种情况），女生时间也扔可用n/2=2=1+1）
   .

4. 女生人数n奇，男生人数m偶 ※
   m = 4： 1 2 3 4
   n = 5：1 1 1 1 1
   min_t =4+2+ (5+1)/2 =9
   （男生正好可配对完，时间为4+2；
   女生为奇数，这时要注意，两两配对会剩一个，需(n+1)/2才可得到正确的时间，或者n/2向上取整也可。）

题目中的样例也可以用这种方法来自己试验一下。

2.2.4奇偶结论

男生人数
m=偶数时，时间求和为2+4+6+8+……+m
m=奇数时，时间求和为1+3+5+7+……+m

女生人数
只有当m为偶数，n为奇数时，求和才为(n+1)/2
其余情况皆为n/2

2.3解题公式总结

min_t是分两部来求的，一部分是男生过桥时间，一部分女生过桥时间，男生过桥时间是总和其实就是一个等差数列求和的结果.
等差数列求和公式为

1. 男生人数m为偶：2+4+6+8+……+m，
   a1=2，项数N（区分女生人数）为m/2，d为2。

Sn = m/2× 2 + (m/2)×(m/2-1)/2×2，
化简后Sn = (m/2)*(m/2+1)

2. 男生人数m为奇：1+3+5+7+……+m，
   a1=1，项数N为(m+1)/2，d为2。

Sn = (m+1)/2+(m+1)/2×((m+1)/2-1)/2×2，
化简后Sn = pow(m+1,2)/4

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int T;
  cin >> T;
  ll N, n, m;
  while (T--) {
    cin >> N >> m;
    n = N-m;//女生人数
    ll sum = 0, sn = 0;
    if (m % 2 == 0)//男生人数为偶数
      sn = (m/2)*(m/2+1); //m/2*2+(m/2)*(m/2-1)/2*2,因a1=2
    else//男生人数为奇数
      sn = pow(m+1,2)/4;  //(m+1)/2+(m+1)/2*((m+1)/2-1)/2*2
    sum = sum + sn + n/2;//男生时间+女生时间
    //m偶n奇情况女生人数要+1
    if (m%2==0 && n%2==1) {
      sum++;
    }
    cout << sum << endl;
  }
}