f467 - 10025 - The ? 1 ? 2 ? ... ? n = k problem
題目描述
題目要求找到最小的 n，使得 ?1?2?...?n = k 成立，其中每個 ? 可以替換為 + 或 -。
解題思路
核心思想是利用二分搜尋來尋找可能的 n 值。對於給定的 n，計算從 1 到 n 的和 (n+1)*n/2。然後，我們需要調整符號，使得表達式的值等於 k。如果 (n+1)*n/2 等於 k，則 n 就是答案。否則，我們需要找到一個最小的 n，使得通過調整符號可以得到 k。
由於每次調整符號，表達式的值會改變 2 的倍數，因此如果 (k - (n+1)*n/2) 是偶數，則存在一種符號組合使得表達式的值等於 k。如果不是偶數，則需要增加 n 的值，直到 (k - (n+1)*n/2) 是偶數。
程式碼使用二分搜尋來找到最小的 n 值，並檢查是否可以通過調整符號得到 k。
複雜度分析
- 時間複雜度: O(log N)，其中 N 是可能的 n 值範圍。二分搜尋的複雜度為 O(log N)，而每次二分搜尋中的計算都是常數時間。
- 空間複雜度: 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 n,t;
inline long long int read(){
long long int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[21],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline long long int fd(long long int l,long long int r){
long long int m=(l+r)/2;
if(l>r)return m;
long long int v=(m+1)*m/2;
if(v>n)
return fd(l,m-1);
else
return fd(m+1,r);
}
int main(){
t=read();
while(t--){
n=read();
if(n<0)n*=-1;
if(n==0){
putchar_unlocked('3');
putchar_unlocked('\n');
}
else{
long long int s=fd(0,n),sv=(s+1)*s/2;
if(sv==n){
write(s);
putchar_unlocked('\n');
}
else{
++s;
sv+=s;
while((sv-n)%2){
++s;
sv+=s;
}
write(s);
putchar_unlocked('\n');
}
}
}
}