e555 - 10170 - The Hotel with Infinite Rooms
題目描述
題目描述了一家無限房間的酒店，旅行團依序入住，每團人數比前一團多一人，且每團入住天數等於其人數。給定第一團人數 a 和目標日期 b，要求計算在第 b 天入住的旅行團人數。
解題思路
這題的核心在於找到一個 n，使得前 n 個旅行團佔用的天數總和剛好大於或等於 b。由於每個旅行團的人數和入住天數都與其在序列中的位置有關，我們可以將問題轉化為求解一個算術級數的和。
具體來說，第 i 個旅行團的人數為 a + i - 1，入住天數為 a + i - 1。因此，前 n 個旅行團佔用的天數總和可以表示為：
sum = (a + a + n - 1) * n / 2 = (2a + n - 1) * n / 2
我們需要找到最小的 n 使得 sum >= b。由於 sum 是一個關於 n 的單調遞增函數，可以使用二分搜尋法來高效地找到這個 n。找到 n 後，入住的旅行團人數為 a + n - 1。
複雜度分析
- 時間複雜度: O(log(100000000))，二分搜尋的複雜度。
- 空間複雜度: O(1)，使用了常數級別的額外空間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
long long int a,b,m,ans;
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
long long int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline long long int bs(long long int l,long long int r){
if(l>r)return l;
m=(l+r)/2;ans=(a+m)*(m-a+1)/2;
return(ans>=b)?bs(l,m-1):bs(m+1,r);
}
int main(){
while(a=read()){
b=read();
write(bs(a,100000000));
putchar_unlocked('\n');
}
}