UVa 10170 – The Hotel with Infinite Rooms

题目：求从s開始的递增序列（每次加1）。求出他们加和不小于D的那个最后的加数。

分析：数学题。分治。s + s+1 + … + n = n*（n+1）/2 – s*（s-1）/2 = （n+s）*（n-s+1）/2。

直接二分答案就可以（二分范围0~10^8）。

说明：(⊙_⊙)。

#include <iostream>
#include <cstdlib> using namespace std;long long sum(long long s, long long n)
{
return (n-s+1LL)*(n+s)/2LL;
}long long bs(int S, long long D)
{
long long mid,l = 1LL,r = 100000000LL;
while (l < r) {
mid = l+(r-l)/2LL;
if (sum(S, mid) >= D)
            r = mid;
        else l = mid+1LL;
}
return r;
}int main()
{
long long s,D;
while (cin >> s >> D)
cout << bs(s, D) << endl;return 0;
}