Anton and Fairy Tale

Created by LXC on Fri Apr 28 11:56:29 2023

https://codeforces.com/problemset/problem/785/C

ranting: 1600

tag: binary search, math

题意

给出两个数n和m, (n,m<=1e18)

有一堆谷共有n颗，

第i天会发生的事：

1. 给这堆谷最多加m颗，最多加到n。
2. 有i只鸟会吃掉i颗，若不足i颗则吃光。

问第几天会吃光。

题解

当m>=n时，必须等到n天才能吃光

否则，
前m天后谷物仍然没有减少。
第m+i天开始，每天会减少m+i颗，但是第二天会增加m。
那么第m+i天鸟吃完后的谷子为f(i) = n-(1+i)*i/2-m。f(i)单调递减，二分找到第一个f(i)<=0则是答案。

注意溢出。

n-(1+i)*i/2-m<=0 变形 sqrt(2*(n-m)-i) <= i这个还是有精度问题。

我们注意到如果经过10^9天那么谷粒将减少大概10^18颗。
所以二分的上界取10^9数量级就行了，比如2e9

找到第一个(1+i)*i/2<=n-m，i in [0, 1e9]。答案为m+i

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, m;
    cin >> n >> m;
    if (m >= n) {
        cout << n << "\n";
    } else {
        ll l = 0, r = 2e9;
        while (l < r) {
            ll x = (r - l) / 2 + l;
            if (n - m <= (1LL + x) * x / 2) {
                r = x;
            } else {
                l = x + 1;
            }
        }
        cout << r + m << "\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}