Note: This article is available in Chinese only. 本文暂无英文版本。
View original
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=966 题意：?1?2?3?4…?n=k,把每个?替换成+或者-，找到最小的n使得式子成立。 题意：这道题最关键的一点是。如果s1=1+2+3+.,x+..+n>=k (所有数取正数）,那么一定有s2=1+2+3+..-x+..+n=k
非严格证明如下：
s1-s2 = 2x,s1-k=2x
一个数减去偶数，奇偶性不变。x是从1到n中的一个，2*x则包含了s1和s2相差的数所有可能性。
具体做法就是找到一个大于等于k的s1,且s1-k是偶数。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年01月28日 星期四 13时58分24秒
4File Name :code/uva/10025.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int k;
34int main()
35{
36 #ifndef ONLINE_JUDGE
37 freopen("code/in.txt","r",stdin);
38 #endif
39 int T;
40 cin>>T;
41 while (T--)
42 {
43 scanf("%d",&k);
44 if (k<0) k = -k;
45
46
47 int sum = 0 ;
48 int p = int(sqrt(2*k));
49
50// cout<<"p:"<<p<<endl;
51 for ( int i = p ; ;i++)
52 {
53 sum = (1+i)*i/2;
54
55
56 if (sum>=k&&(sum-k)%2==0&&sum>0)
57 {
58 cout<<i<<endl;
59 break;
60 }
61 }
62 if (T)
63 {
64 puts("");
65 }
66 }
67
68 #ifndef ONLINE_JUDGE
69 fclose(stdin);
70 #endif
71 return 0;
72}