出题人题解

Writer: Yue_chen

题意

给出 $n$ 场比赛的表现分，求rating到达1e8所需要的最小初始rating。

分析

题目中第 $i$ 的加减分都与当前的rating相关，而当前rating和初始rating和前$i - 1$不进行O(n)暴力枚举，几乎不可能完成精确计算。但是将初始rating从0枚举到1e9显然是不可能的。

我们发现初始rating与最终rating是呈正相关的，也就是具备单调性。对于单调性极限问题，可以使用二分算法进行优化，枚举rating时间复杂度$O(log_2y) = 31$ ，总复杂度$O(nlog_2y)$

还有一个小技巧，一般求 yyy 达到某个阈值时，xxx 的最大/最小值，很有可能就是二分。

代码

using namespace std;

using i64 = long long;

void solve() {
	int n; cin >> n;
	
	vector<i64> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	//局部内函数写法，看不懂的写在函数外面就行
	auto check = [&](i64 x) {
		for (int i = 1; i <= n; i++) {
      //llabs long long类型绝对值函数
			if (a[i] > x) x += llabs(a[i] - x) / 100;
			else x -= llabs(a[i] - x) / 100;
		}
		return x >= 1e8;
	};

  //二分算法
	i64 l = -1, r = 1e9+1;
	while (r - l > 1) {
		i64 mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	if (r == 1e9+1) cout << "-1\n";
	else cout << r << "\n";
}

signed main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

神秘知识拓展

我们发现初始rating对第一场比赛后rating的影响程度是$0.99$，那么对第二场比赛后的影响就是$0.99^2$，以此类推，当$0.99^n$无限接近于0时，初始rating将不会再影响最终rating。如果 $n$ 比较小，这意味着只需要暴力枚举最后 $n$ 场比赛即可得知最终的 rating。

当然，为了防止这种情况的发生，我修改了rating的范围，想要在底数为0.99的情况下不影响1e9级别的数，这个 $n$ 将会大的离谱。