O(log(x))复杂度代码遇TLE求优化(Codeforces 2082B)
Codeforces 2082B 超时问题优化求助
以下是我为Codeforces竞赛2082B题编写的代码:
#include <bits/stdc++.h> void solve() { int x, floor, ceil; std::cin >> x >> floor >> ceil; int maxX = x, minX = x; int floorMax = floor, ceilMax = ceil; while(maxX && (floorMax || ceilMax)) { if (maxX % 2) { if (ceilMax) { maxX = (maxX + 1) / 2; ceilMax--; } else { maxX /= 2; floorMax--; } } else { if (floorMax) { maxX /= 2; floorMax--; } else { ceilMax--; maxX = (maxX + 1) / 2; } } } while(minX && (floor || ceil)) { if (minX % 2 == 0) { if (ceil) { minX = (minX + 1) / 2; ceil--; } else { minX /= 2; floor--; } } else { if (floor) { minX /= 2; floor--; } else { ceil--; minX = (minX + 1) / 2; } } } std::cout << minX << ' ' << maxX << '\n'; } signed main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int t; std::cin >> t; while (t--) { solve(); } return 0; }
该代码时间复杂度为O(log(x)),符合题目输入约束,但运行时出现超时(TLE),最优成绩为1208ms,而题目时限为1000ms。我已尝试以下优化:
- 关闭stdio同步、解绑cin/cout
- 改用C风格IO
- 逻辑优化(如减少额外变量)
但问题仍未解决,我认为O(log(x))的解法理应可行,希望得到进一步的优化建议。
内容的提问来源于stack exchange,提问作者lunatic_since_C
相关产品推荐
相关产品推荐

