牛客阿牛哥：又来?内部KPI压力挺大的噢，海量hc

livefreely：用 i 步走到 target 数值，其实就是用 1,2,..,i 这 i 个数字，每个数字前面插入 + 号或 - 号，运算得到 target 。 1 到 i 到和是 (1+i)i/2 ，假设已经确定 i 了，那么可以把这 i 个数字分成两个子列 {x}, {y} , 把这两个子列各自的和记为 X，Y 。那么有 可以得到 ,所以逐渐增加 i ，找到第一个满足这个公式的正整数X，此时 i 就是要求的值。 我就接着这写了。为了简单起见，下面令t=target， 1）（必要条件,但不一定是充分条件）可以肯定的是对于给定的target，对应的所有可能的解一定满足： 由此，我们可以得到 因为Y必须是整数，所以由知，如果i是原问题的一个解，那么必须有： 且奇偶性相同。于是我们可以猜想：最优解就是满足上述条件的最小值。代码如下：int  int getStep(int N) {     int res=0;     int s=0;     while(s<N||s%2!=N%2)     {         ++res;         s+=res;     }    return res; } 下面给出上述结果的充分性证明。 2）（充分性）如果找到一个i使得由 确定的X,Y是整数，那么一定存在原问题的解，即存在集合的一个划分：,使得成立。其中P由取正号的数组成，N由取负号的数组成。 废话不多说。我们只要证满足的Y能表示成的一个子集所有元素和的形式。为此，我们将命题进行推广（至于为什么想到推广，完全来源于直觉以及以往的证明经验）得下面一个有趣的定理。 为了简单起见，我们用，其他开区间、闭区间类似。 定理1  , 有了这个定理，由,就可以证明上述的充分条件。下面是关于定理1的证明，有兴趣的可以看一下。 直白地说，就是从随便取出一些元素相加就可以得到0到之间的任何元素。我们举个例子如下：，则有 上面的例子按照特定的规则生成了所有1~10之间所有的数，至于0的生成取空集即可，即。 证明如下： 首先列举所有1个元素组成的和，得到区间, 然后列举2个元素组成的和，得到区间, 然后是3个元素的和，得到区间, ~~~~~ 最后是i个元素的和，得到区间 我们要证明两点 1）所有j个元素的和刚好组成一个区间 2）区间之间没有空隙。 首先证明区间没有空隙。 我们考虑相邻的两个区间 没有空隙等价于 , 这是很容易证明的。因为表示最大的由j个元素组成的和 所以如果j不等于i，那么一定有 , 两边加1，便可得到所要证明的结论。 为什么所有j个元素的和刚好组成一个区间呢？我们可以按照上面例子中的方法进行说明。 a）首先是最小的由j个元素组成的和，即,pos=j-1 b）如果V[pos]<V[pos+1]-1，下一个j个元素就是将V[pos]加1，否则就pos=pos-1，然后再V[pos]++。 知道pos<0为止。 在这个过程下一组数刚好是将前一组数中的某一个数加1得到，且始终保持V中元素是严格递增的（也就不会重复）。刚好可以列举出 之间所有的元素。 可以参考下面的伪代码 int pos=j-1; int V[]={1,2,3,....,j,i+1} while(pos!=-1) { for(int k=0;k<j;++k)cout<<V[k]<<" "; cout<<endl; if(V[pos]==V[pos+1]-1)--pos; ++V[pos]; } 至此，已经完成了定理1的证明。但是对于一个对数学的美有着特别追求的人，我还想到了另一个简单的基于数学归纳法的证明方法。 证明如下： 假设对于i命题已经成立，那么下面证明命题对i+1也成立。 对于i，最大的一个元素和是,接下来按照下面的顺序进行列举 上述列举保证了下一行比上一行刚好大1，一共有i+1列 所以可以一直列举到i+1时的最大元素. 这便证明了定理1. 我之前还想过一个问题，来源于找零钱的编程题。 问题如下：集合 包含了那些整数呢？上面所有的数都是整数，是给定的一些币值。 例如，给你币值为1,2,5的三种硬币，是不是能组合出所有的钱数呢？ ~~~~~~ 是不是感觉所有的正整数都能凑出来！！！ 再看一个例子 给定币值2、4，那么肯定凑不出3. 因为无论怎么凑，只能凑出个偶数来。 有兴趣的可以在好好想一想 结论是：存在一个足够到的N使得下面的结论成立： 即对于充分大的N，所求集合和最大公约数组成的集合相等。 说明：我也很菜，笔试的时候想着用广度优先去做，结果代码还没敲完时间就到了。只是心里一直放不下这个题，所以才写写感想。