526互联

Codeforces Round 861 (Div. 2) A. Lucky Numbers

发布时间 2023-09-05 21:22:53作者: zsxuan

定义一个数的幸运值是这个数的数位的最大值减去最小值，如 \(luckiness_{769} = 9 - 6 = 3\) 。给出 \(l\) \(r\) ，求 \([l, r]\) 中最幸运的数，若最幸运的数有多个，任意一个为答案。

考虑拆分数位，然后枚举。以 \(O(d)\) 的复杂度计算幸运值。则线性扫一遍的复杂度为 \(O(n d)\) 。由 \(1 \leq l < r \leq 10^6\) ， \(d_{max} = 6\) 。\(t\) 组数据的上限复杂度为 \(O(t n d)\) ，达到 \(1E9\) 级别。

性质：连续 \(100\) 个数中对 \(100\) 取模的余数取遍 \([0, 99]\) ，也就是最后两位取遍 \([0, 99]\) 。

于是可以 \(O(1)\) 计算答案，遍历 \([l, min(l + 99, r)]\) 即可。

view 
#include <bits/stdc++.h>
void solve() {
	int l, r; std::cin >> l >> r; r = std::min(l + 99, r);
	auto get = [&](int x) {
		std::vector<int> d;
		while (x) {
			d.push_back(x % 10);
			x /= 10;
		}
		return *max_element(d.begin(), d.end()) - *min_element(d.begin(), d.end());
	};
	int mx = 0, p = l;
	for (int i = l; i <= r; i++) if (mx < get(i)) { mx = get(i); p = i; }
	std::cout << p << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}