b003 - 運算式 + - 符號設定問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求找到最小的 n 值，使得 ± 1 ± 2 ± 3 ± ... ± n = k 成立。其中，每個數字前可以選擇加號或減號，目標是找到滿足等式的最小 n。

解題思路

核心思想是利用二分搜尋法來尋找可能的 n 值。首先，計算從 1 到 n 的和，即 n * (n + 1) / 2。然後，檢查是否存在一種符號組合，使得這個和等於目標值 k。

由於符號可以任意選擇，因此和的範圍是 [-n * (n + 1) / 2, n * (n + 1) / 2]。如果 k 超出這個範圍，則不存在解。

如果 k 在範圍內，則可以通過調整 n 的值，並檢查是否存在滿足條件的符號組合。程式碼中，bs 函數使用二分搜尋來找到一個可能的 n 值，使得 n * (n + 1) / 2 接近 k。

找到可能的 n 值後，程式碼會迭代增加 n，直到找到一個 n 值，使得 (n * (n + 1) / 2 - k) 是偶數。這是因為如果 n * (n + 1) / 2 - k 是偶數，則可以通過調整最後一個數字的符號來使等式成立。

複雜度分析

• 時間複雜度: O(log(a))，其中 a 是輸入的 k 值。二分搜尋的複雜度為 O(log(a))，而後面的 while 迴圈最多執行常數次。
• 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
long long int a;
long long int bs(long long int l,long long int r){
	long long int m=(l+r)/2,mm=((1+m)*m)/2;
	if(mm==a)return m;
	if(l>r)return l;
	if(mm>a)
		bs(l,m-1);
	else
		bs(m+1,r);
}
int main(){
	while(cin >> a){
		if(a<0)a*=-1;
		long long int fd=bs(0,a);
		while(((fd*(fd+1)/2)-a)%2)
			++fd;
		cout << fd << "\n"; 
	}
}