e635 - 12908 - The book thief

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Anita 在計算一本書的頁碼總和時，不小心漏加了一頁。給定 Anita 計算得到的總和 s，要求找出漏加的頁碼以及書的總頁數。

解題思路

題目要求找到一個頁碼 x 和一個頁數 n，使得 n * (n + 1) / 2 - x = s。我們可以將這個問題轉化為找到一個 n，使得 n * (n + 1) / 2 大於或等於 s，然後計算出 x。由於 n 的範圍較大，可以使用二分搜尋法來快速找到滿足條件的 n。

具體來說，我們定義一個函數 ans(l, r)，使用二分搜尋在 l 到 r 的範圍內尋找滿足 (m + 1) * m / 2 > s 的最小 m。找到 m 後，書的總頁數為 m，漏加的頁碼為 (m + 1) * m / 2 - s。

複雜度分析

• 時間複雜度: O(log N)，其中 N 是可能的頁數上限 (10^8)。二分搜尋的複雜度為 O(log N)。
• 空間複雜度: O(1)，使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
long long int s;
long long int ans(long long int l,long long int r){
	if(l>r)return l;
	long long int m = (l+r)/2,n = ((m+1)*m)/2;
	if(n>s){
		return ans(l,m-1);
	}
	else{
		return ans(m+1,r);
	}
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> s){
		if(s==0)break;
		int tmp = ans(0,100000001);
		cout << ((tmp+1)*tmp)/2-s << " " << tmp << "\n";
	}
}