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