标签：二分 Klee int mid long 最小 leq 绝对值 数组

Klee's SUPER DUPER LARGE Array!!!

每次测试时间限制：2秒

每次测试的内存限制：256 MB

题目描述

Klee 拥有一个长度为 n 的数组 a，数组中的元素依次为 [k, k + 1,..., k + n - 1]。Klee 希望选择一个索引 i（1≤i≤n），使得 x = |a1 + a2 + ⋯ + ai - ai+1 - ⋯ - an| 最小。其中对于任意整数 z，|z| 表示 z 的绝对值。要求输出 x 的最小值。

输入格式

第一行包含 \(t\) （ \(1 \leq t \leq 10^4\) ）—测试用例的数量。

每个测试用例包含两个整数 \(n\) 和 \(k\) （ \(2 \leq n, k \leq 10^9\) ）—数组的长度和数组的起始元素。

输出格式

对于每个测试用例，在新的一行上输出 \(x\) 的最小值。

样例 #1

样例输入 #1

4
2 2
7 2
5 3
1000000000 1000000000

样例输出 #1

1
5
1
347369930

提示

注意

在第一个示例中， \(a = [2, 3]\) 。当选择 \(i = 1\) 时， \(x = |2-3| = 1\) 。可以看出，这是 \(x\) 的最小可能值。

在第三个样本中， \(a = [3, 4, 5, 6, 7]\) 。当选择 \(i = 3\) 时， \(x = |3 + 4 + 5 - 6 - 7| = 1\) 。可以看出，这是 \(x\) 的最小可能值。

---

---

---

---

---

题解

注意到本题中，最后一个样例过大，而题设的数组是公差为1的等差数列，很容易想到，等差数列求和公式。（死去的高中知识怎么在攻击我？？）

\[S_n = \frac{n(a_1 + a_n)}{2} ~~~~~ 或者 ~~~~~ S_n = \frac{n[2a_1 + (n-1)d]}{2} \]

#include <iostream> 
using namespace std;

long long n, l, r, mid;
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		long long k;
		scanf("%d%lld", &n, &k);

		l = 0; r = n;
		long long  ans = 0;
		for (int i = 1; i < n; i++) {
		}
		ans =10 * (n+k);

		while (l <= r) {
			mid = (l + r) >> 1;

			long long sum = 0; int num = 0;
			int nn = n;


			long long add = 0, sub = 0;

			//等差数列求和；死去的记忆正在攻击我
			add = mid * (2 * k + mid - 1) / 2;
			sub = (n - mid)*(2 * k + n + mid - 1) / 2;

			sum = add - sub;


			long long sum1 = abs(sum);
			if (sum1 <= ans) ans = sum1;


			if (sum > 0) r = mid - 1;
			else l = mid + 1;

		}
		printf("%d\n", ans);
	}
	return 0;
}

标签：二分,Klee,int,mid,long,最小,leq,绝对值,数组
From： https://www.cnblogs.com/phuzzz/p/18545853