e658 - 11614 - Etruscan Warriors Never Play Chess

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定數量 n 的戰士，可以排成多少行，其中第 i 行有 i 個戰士，且剩餘的戰士不足以組成下一行時，不計算該行。

解題思路

題目可以轉化為求解最大的整數 k，使得 1 + 2 + ... + k <= n。 等號左邊是等差數列的和，可以表示為 k * (k + 1) / 2 <= n，進而得到 k * (k + 1) <= 2 * n。 由於 k 是一個整數，我們可以通過二分搜尋來找到滿足這個不等式的最大 k 值。

程式碼中，bs 函數實現了二分搜尋。它在 l 到 r 的範圍內搜尋，計算 sqrt(2*n - m) 的值，並根據這個值與 m 的大小關係來調整搜尋範圍。

複雜度分析

• 時間複雜度: O(log(mmax))，其中 mmax 是 mmax 的值，因為使用了二分搜尋。
• 空間複雜度: O(1)，因為只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <cmath>
using namespace std;
long long int mmax=1000000000000000000,n;
long long int bs(long long int l,long long int r){
	if(l>r)return r;
	long long int m=(r+l)/2,all=sqrt(2*n-m);
	if(all<m)
		return bs(l,m-1);
	else if(all>m)
		return bs(m+1,r);
	return m;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		cout << bs(1,mmax) << "\n";
	}
}