CF1612C Chat Ban

题意

有一个大小为k的那个图形 ， 问第x个在第几行，如果超出范围输出2*k-1

思路：

可以用求和公式 (首项 + 末项) * 项数 / 2来快速算出个数。
通过观察可以发现一张图里的总个数可以用k * k来表示
分情况讨论：

• x >= 总个数，输出2*k-1
• x 在上半部分，我们就确定l = 0, r = k， 在此范围内二分出一个最大的能使结果小于x的末项。
• 如果在下半部分，那么我就反过来求，用总个数 - 要找的个数，结果肯定在下半部分，那么就和和上一步同理了。

难点在于二分的使用

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x, k;signed main()
{
    int t; cin >> t;while (t -- ){
    cin >> k >> x;int flag = (1 + k) * k / 2;if(x >= k * k) {
    cout << 2 * k - 1 << endl;continue;}if (x <= (1 + k) * k / 2){
    int l = 0, r = k;int mid;int ans = 0;while (l <= r){
    mid = (l + r) / 2;if ((1 + mid) * mid / 2 >= x) ans = mid, r = mid - 1;else l = mid + 1;}cout << ans << endl;}else{
    	int mid;int l = 0, r = k - 1;x = k * k - x;int ans;while (l <= r){
    mid = (l + r) >> 1;if ((1 + mid) * mid / 2 <= x) l = mid + 1;else ans = 2 * k - mid, r = mid - 1;}cout << ans  << endl;//倒过来找时要正着减一下 }}return 0;
}