题意 :
- 有 2 k − 1 2k-1 2k−1行,且1-k行递增,k+1行-2k-1行递减,发大于等于x个表情后会被封号,问最多发出多少行,发生“超出”行为的那行也累加答案中
思路 :
- 范围太大了,只能用二分来做
- 分前半段和后半段来考虑,二分时边界取大一点
- 发现后半段如果第k+1行看作第一行,那么第i行的表情数就是k-mid
- ans(最终结果)更新(当前mid如果合法就更新)时注意和边界判断
- 后半段二分的时候,L也是从1算起,为了扩大二分范围,L初始化为0
- setprecision在头文件iomanip中
#include#include using namespace std; using ll = long long; int main() { cin.tie(nullptr) -> sync_with_stdio(false); cout << fixed << setprecision(20); int _ = 1; cin >> _; while (_ -- ) { ll k, x; cin >> k >> x; ll half = (1 + k) * k / 2; ll ans = 1; if (x <= half) { ll L = 0, R = k + 1; while (L < R) { ll mid = L + R >> 1; ll now = (1 + mid) * mid / 2; if (now < x) { ans = min(2 * k - 1, mid + 1); L = mid + 1; } else R = mid; } } else { ans = k; ll L = 0, R = k + 1; while (L < R) { ll mid = L + R >> 1; ll now = (k - 1 + k - mid) * mid / 2 + half; if (now < x) { ans = min(2 * k - 1, k + mid + 1); // 不要忘了加上k L = mid + 1; } else R = mid; } } cout << ans << endl; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)