CodeForces 785C Anton and Fairy Tale 二分

题意：

有一个谷仓容量为(n)，谷仓第一天是满的，然后每天都发生这两件事：

1. 往谷仓中放(m)个谷子，多出来的忽略掉
2. 第(i)天来(i)只麻雀，吃掉(i)个谷子

求多少天后谷仓会空

分析：

分类讨论：

1. (n leq m)

每天都会把谷仓放满，所以第(n)后会变空

2. (n > m)

前(m)天后谷仓还一直都是满的
第(m+1)天后还剩(n-m-1)，第(m+2)天后还剩(n-m-1-2)
第(m+i)天后还剩(n-m-frac{i(i+1)}{2})
所以可以二分求出答案

注意到比较(n-m>frac{i(i+1)}{2})时，中间计算结果会溢出
所以可以通过除法来比较大小，令(t=frac{2(n-m)}{i(i+1)})

• (t>1)，有(n-m>frac{i(i+1)}{2})
• (t=0)，有(n-m<frac{i(i+1)}{2})
• (t=1)，这时(i(i+1))的值不会太大，可以通过直接计算比较大小

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

LL n, m;

bool ok(LL x) {
	x -= m;
	LL t = n - m;

	t <<= 1;
	t /= x;
	t /= x + 1;

	if(t > 1) return false;
	if(!t) return true;
	return n - m == x * (x + 1) / 2;
}

int main()
{
	scanf("%lld%lld", &n, &m);
	if(n <= m) {
		printf("%lld
", n);
		return 0;
	}

	LL L = m + 1, R = n;
	while(L < R) {
		LL M = (L + R) / 2;
		if(ok(M)) R = M;
		else L = M + 1;
	}

	printf("%lld
", L);

	return 0;
}