8.29 字节笔试 第一题

同求大神讲解 用最蠢的方法蒙了50.。。

(i的总和 > abs(两数之差)) && (i的总和 - abs(两数之差)) % 2 == 0 则可以

#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() {     int T; cin >> T;     while(T--) {         LL a, b; cin >> a >> b;         LL k = abs(a - b);         LL l = -1, r = 1e5;         while(l + 1 < r) {             LL mid = l + r >> 1;             if(mid*(mid+1)/2 <= k) {                 l = mid;             } else {                 r = mid;             }         }         while(l*(l+1)/2 < k || (l*(l+1)/2-k)&1) ++l;         cout << l << endl;     }     return 0; }

利用奇偶性，给的数据不重要，a-b的差值的绝对值重要，结果是累加和刚好>=（a-b的差值的绝对值）的奇数或偶数，要做 一些条件判断，大体思路就这

差值need = Math.max(a, b) - Math.min(a, b)。然后按序1，2，3...累加sum，直到满足sum - need >= 0 && (sum - need) % 2 == 0，就说明可以填充差值且可以将剩下的数字平分给两个数，让他们相等。

这道题有规律，时间复杂度可以做到O(1)

数学找规律吧，两个数的差值为 x, 从1,2,3,... n 的和为(n+1)*n/2 记为y，要让 y 满足 (y-x)%2 == 0， 因为需要填差值，并且让两者相等。暴力点就是让n 从1遍历到10^5，找到第一个满足的。优化的话使用二分查找，left=0，right=10^5

用bfs 当成二叉树做，先求出两个数abs 然后定义level为0; 每遍历一层+1，出队后要么+level要么-level，出队后得出的值如果等于两个数绝对值则return level

树状数组。。。。

a b两个数字，假设a比较小，那么你就一直往a上加i，直到a-b的差为偶数

第一题我的思路：1+2+3+4+.......>=abs(A-B)且(1+2+3+4+.......+abs(A-B))%2==0,全过