CodeForces 785C Anton and Fairy Tale【二分答案+思维】

时间:2022-09-07 18:37:50

题目链接:http://codeforces.com/contest/785/problem/C
题意:给你一个谷仓,容量为n,每天往谷仓里放m斤粮食,然后第i天从谷仓拿i斤粮食,问你几天后谷仓第一次空
解析:很明显的二分答案,但是我犹豫了,因为我n和m有点大,不过仔细想想,递减的是平方量级的,所以在int范围内,谷仓一定会出现第一次空,那么剩下的就是二分了,前m天其实是没有拿东西的概念的因为拿了又填满了,而第m+1天起,谷仓会被拿走1斤粮食,以此类推,不过有个点要注意的就是,如果m>n的话,第n天粮食就拿完了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int inf = 0x7fffffff;
long long n,m;
int main()
{
    scanf("%I64d %I64d",&n,&m);
    n -=m;
    long long l = 0,r = 0x7fffffff;
    while(l<r)
    {
        long long mid = (l+r)/2;
        if(mid*(mid+1)/2>=n)
            r = mid;
        else
            l = mid+1;
    }
    printf("%I64d\n",n<0?n+m:r+m);
    return 0;
}