评论详情-牛客网

用 i 步走到 target 数值，其实就是用 1,2,..,i 这 i 个数字，每个数字前面插入 + 号或 - 号，运算得到 target 。

1 到 i 到和是 (1+i)i/2 ，假设已经确定 i 了，那么可以把这 i 个数字分成两个子列 {x}, {y} , 把这两个子列各自的和记为 X，Y 。那么有

可以得到

,所以逐渐增加 i ，找到第一个满足这个公式的正整数X，此时 i 就是要求的值。

我就接着这写了。为了简单起见，下面令t=target， ${S_i} = (1 + i)i/2$

1）（必要条件,但不一定是充分条件）可以肯定的是对于给定的target，对应的所有可能的解一定满足：

$\left\{ \begin{array}{l} X + Y = {S_i}\\ X - Y = t\\ X,Y \ge 0 \end{array} \right.$

由此，我们可以得到

$\left\{ \begin{array}{l} X = ({S_i} + t)/2\\ Y = ({S_i} - t)/2\\ X,Y \ge 0 \end{array} \right.$

因为Y必须是整数，所以由 $Y = ({S_i} - t)/2$ 知，如果i是原问题的一个解，那么必须有：

${S_i}\ge t$ 且 ${S_i}和 t$ 奇偶性相同。于是我们可以猜想：最优解就是满足上述条件的最小值。代码如下：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使得由

$\left\{ \begin{array}{l} X + Y = {S_i}\\ X - Y = t\\ X,Y \ge 0 \end{array} \right.$

确定的X,Y是整数，那么一定存在原问题的解，即存在集合 $I = \{ 1,2, \cdots ,i\}$ 的一个划分： $(P,N)满足P \cup N = I,P \cap N = \emptyset$ ,使得 $\sum\limits_{x \in P} x - \sum\limits_{y \in N} y = t$ 成立。其中P由取正号的数组成，N由取负号的数组成。

废话不多说。我们只要证满足 $Y = ({S_i} - t)/2$ 的Y能表示成 $I = \{ 1,2, \cdots ,i\}$ 的一个子集所有元素和的形式。为此，我们将命题进行推广（至于为什么想到推广，完全来源于直觉以及以往的证明经验）得下面一个有趣的定理。

为了简单起见，我们用 $[m,n] = \{ i|i是整数且m \le i \le n\}$ ，其他开区间、闭区间类似。

定理1 $\{ x|x = \sum\limits_{e \in A} {e且A \subset I} \} = [0,{S_i}]$ , $其中I = \{ 1,2, \cdots ,i\} 以及{S_i} = (1 + i)i/2$

有了这个定理，由 $Y = ({S_i} - t)/2\le S_i$ ,就可以证明上述的充分条件。下面是关于定理1的证明，有兴趣的可以看一下。

直白地说，就是从 $I = \{ 1,2, \cdots ,i\}$ 随便取出一些元素相加就可以得到0到 ${S_i} = (1 + i)i/2$ 之间的任何元素。我们举个例子如下： $I = \{ 1,2, \cdots ,4\}$ ，则有

$\begin{array}{l} 1 = 1\\ 2 = 2\\ 3 = 3 = 1 + 2\\ 4 = 4 = 1 + 3\\ 5 = \;\;\;\;\;\;\;1 + 4\\ 6 = \;\;\;\;\;\;\;2 + 4 = 1 + 2 + 3\\ 7 = \;\;\;\;\;\;\;3 + 4 = 1 + 2 + 4\\ 8 = \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 + 3 + 4\\ 9 = \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2 + 3 + 4\\ 10 = \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 + 2 + 3 + 4 \end{array}$

上面的例子按照特定的规则生成了所有1~10之间所有的数，至于0的生成取空集即可，即 $0 = \sum\limits_{e \in \emptyset } e$ 。

证明如下：

首先列举所有1个元素组成的和，得到区间

然后列举2个元素组成的和，得到区间

然后是3个元素的和，得到区间

~~~~~

最后是i个元素的和，得到区间 $[1 + 2 + \ldots + i,1 + 2 + \ldots + i]$

我们要证明两点

1）所有j个元素的和刚好组成一个区间

2）区间之间没有空隙。

首先证明区间没有空隙。

我们考虑相邻的两个区间

$[\sum\limits_{k = 1}^j k ,\sum\limits_{k = 1}^j {(i - k + 1)} ],[\sum\limits_{k = 1}^{j + 1} k ,\sum\limits_{k = 1}^{j + 1} {(i - k + 1)} ]$

没有空隙等价于

$\sum\limits_{k = 1}^{j + 1} k \le 1 + \sum\limits_{k = 1}^j {(i - k + 1)}$ ,

这是很容易证明的。因为 $\sum\limits_{k = 1}^j {(i - k + 1)}$ 表示最大的由j个元素组成的和

所以如果j不等于i，那么一定有

$\sum\limits_{k = 1}^j {(i - k + 1)} \ge \sum\limits_{k = 2}^{j+1} {k}$ ,

两边加1，便可得到所要证明的结论。

为什么所有j个元素的和刚好组成一个区间呢？我们可以按照上面例子中的方法进行说明。

a）首先是最小的由j个元素组成的和，即 $V[]=\{1,2,3, \cdots ,j,i+1\}$ ,pos=j-1

b）如果V[pos]<V[pos+1]-1，下一个j个元素就是将V[pos]加1，否则就pos=pos-1，然后再V[pos]++。

知道pos<0为止。

在这个过程下一组数刚好是将前一组数中的某一个数加1得到，且始终保持V中元素是严格递增的（也就不会重复）。刚好可以列举出 $最小元素和1 + 2 + \cdots + j到最大元素和i - (j - 1) + i - (j - 2) + \cdots + i$

之间所有的元素。

可以参考下面的伪代码

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 + 2 + \cdots + i$ ,接下来按照下面的顺序进行列举

$\begin{array}{l} 1 + 2 + 3 + \cdots + (i - 2) + (i - 1) + i\\ 1 + 2 + 3 + \cdots + (i - 2) + (i - 1) + (i + 1)\\ 1 + 2 + 3 + \cdots + (i - 2) + (i - 1 + 1) + (i + 1)\\ 1 + 2 + 3 + \cdots + (i - 2 + 1) + (i - 1 + 1) + (i + 1)\\ \vdots \\ 1 + 2 + (3 + 1) + \cdots + (i - 2 + 1) + (i - 1 + 1) + (i + 1)\\ 1 + (2 + 1) + (3 + 1) + \cdots + (i - 2 + 1) + (i - 1 + 1) + (i + 1)\\ (1 + 1) + (2 + 1) + (3 + 1) + \cdots + (i - 2 + 1) + (i - 1 + 1) + (i + 1) \end{array}$

上述列举保证了下一行比上一行刚好大1，一共有i+1列

所以可以一直列举到i+1时的最大元素 ${S_{i + 1}} = {S_i} + i + 1$ .

这便证明了定理1.

我之前还想过一个问题，来源于找零钱的编程题。

问题如下：集合

$\{ s|s = \sum\limits_i {{x_i}{a_i}} ,\forall i\;{x_i} \ge 0\}$ 包含了那些整数呢？上面所有的数都是整数， ${a_i}$ 是给定的一些币值。

例如，给你币值为1,2,5的三种硬币，是不是能组合出所有的钱数呢？

$\begin{array}{l} 1 = 1\\ 2 = 2\\ 3 = 1 + 2\\ 4 = 2 + 2\\ 5 = 5\\ 6 = 1 + 5\\ 7 = 2 + 5\\ 8 = 1 + 2 + 5\\ 9 = 2 + 2 + 5\\ 10 = 5 + 5\\ 11 = 1 + 5 + 5 \end{array}$

~~~~~~

是不是感觉所有的正整数都能凑出来！！！

再看一个例子

给定币值2、4，那么肯定凑不出3.

因为无论怎么凑，只能凑出个偶数来。

有兴趣的可以在好好想一想

结论是：存在一个足够到的N使得下面的结论成立：

$\{ s|s = \sum\limits_i {{x_i}{a_i}} ,\forall i\;{x_i} \ge 0\} \cap \{ s|s > N\} = \{ s|s = k\gcd ({a_1},{a_2}, \cdots ,{a_n}),k > 0\} \cap \{ s|s > N\}$

即对于充分大的N，所求集合和最大公约数组成的集合相等。

说明：我也很菜，笔试的时候想着用广度优先去做，结果代码还没敲完时间就到了。只是心里一直放不下这个题，所以才写写感想。