The ? 1 ? 2 ? ... ? n = k problem
The problem
Given the following formula, one can set operators '+' or '-' instead of each '?', in order to obtain a given k
? 1 ? 2 ? ... ? n = k
For example: to obtain k = 12 , the expression to be used will be:
- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12
with n = 7
The Input
The first line is the number of test cases, followed by a blank line.
Each test case of the input contains integer k (0<=|k|<=1000000000).
Each test case will be separated by a single line.
The Output
For each test case, your program should print the minimal possible n (1<=n) to obtain k with the above formula.
Print a blank line between the outputs for two consecutive test cases.
Sample Input
2 12 -3646397
Sample Output
7 2701
()1()2()3()……()n=k
要求在括号内填入加号或者减号,使得这n个数能够得到k。求n的最小值
思路:前n个数全部加起来之后,再把其中的几个加号调整为减号,便可以得到k。
那么,必须保证前n个数相加大于等于k。如果等于,就直接输出。如果不等于,那么调整减号,而且必须要注意到,每次调一个减号,减去的是偶数,而且减去的最小值为2
随意要保证前n个数的和的奇偶性和k相同
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int main () { int k,n,i,t,sum; cin>>t; while(t--) { cin>>k; k=fabs(k); n=pow(k,1/2); sum=(1+n)*n/2; while(sum<k) { n++; sum+=n; } if (sum==k) printf("%d\n",n); else { if (sum<k+2) { n++; sum+=n; } while (k%2!=sum%2) { n++; sum+=n; } printf("%d\n",n); } if (t!=0) cout<<endl; } return 0; }