Chat Ban 二分,等差数列

Chat Ban 二分,等差数列,第1张

Chat Ban 二分,等差数列


题意 :

  • 有 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;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5594887.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存