2018腾讯秋招算法笔试题

小Q和牛牛玩了一个游戏，这个游戏进行了若干轮，每一轮都有一一个获胜者，获胜者将获得轮次的分数。 例如:第一轮小Q获胜，小Q将获得1分,第二轮牛牛获胜，牛牛将获得2分。 游戏结束后，小Q总共获得了x分，牛牛获得了y分。现在希望你能来计算一下小Q在所有轮次中获胜次数最少可以是多少。 更一般的，假设总共进行了N轮游戏,小Q最少需要在N轮中获胜多少次，使得小Q恰好获得x分，牛牛获得y分。

输入描述:

输入包括两个整数x,y(0 < x, y <=1012)，表示小q获得的分数和牛牛获得的分数。

输出描述:

输出一一个正整数，表示小q最少进行的轮数，如果没有解，输出-1。

示例：

输入：

7 14

输出：

2

代码：

long long x, y, N;
int t = 0, sum = 0,flag = 0;
cin >> x;
cin >> y;
for (N = 0; N <= (x > y ? x : y); N++){
    if ((x + y) != (N*(N + 1) / 2))
      flag = 0;
    else{
      flag = 1;
      break;
    }
}
if (flag == 1){
    while (x >= 0){
        if (x <= N){
          sum = t + 1;
          break;
    }
    if (x > N){
      x = x - N;
      t += 1;
      N -= 1;
    }
 }
  cout << sum;
}
else
    cout << -1;

解题思路：

由题意可知求解N只用根据：x+y=∑N 来求解N。而x,y种必定有一个数是包含N的，直接选取x,y中的最大值设置为N的最大值。接下来求解小Q至少获取多少次。这就要求小Q在轮次数高的时候多次获胜，首先判断是否比N大，当比N小时，直接在该轮次获胜，那么小Q只获取一次。当比N大时，首先，在N轮的时候获胜，那么剩下的积分就是x-N，再对剩下的N-1轮运用此方法，最终求解出最少次。

对示例进行分析：（7+14）=（1+N）*N/2

求解出N=6

此时7>6 则表明小Q再第六轮获胜，7-6=1<6，则表明小Q再第一轮获胜即可，因此结果为2

注：求解N的时候可以用求解方程的解的方式求解，最后需要判断N是否为整数。