poj 1844 sum (数学)

题意：给出一个数S，从1到N个数，每个数前面可以是负号或者是正号，这样累加起来，结果可以等于S，问最小的N是多少。

题解：因为从1一直加到n的值（假设为sum(n)）等于sum的n是最小的。所以我们先算出sum(n)大于等于sum的那个n。

这样我们可以得出一个值m = sum(n) - sum.如果m==0那么n就是我们要求的最小的n。否则

因为你减一个数相当于在sum(n)里减去这个数的两倍。

所以如果m是奇数的话，那么这时你不可能在前面把某些+号变成-号，使得其值等于sum。

因此m必须是偶数，如果不是偶数，则使n=n+1,继续判断，直到为偶数为止。

又因为m/2这个数一定会在1到n之间的，所以此时的n刚好是最小的。

代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define eps 1e-7

int main(){
    //freopen("C:\\Users\\dengzt\\Desktop\\in.txt","r",stdin);
    //freopen("C:\\Users\\dengzt\\Desktop\\out.txt","w",stdout);
    int sum, n, m;
    while(cin>>sum){

        double i = (sqrt(8*sum+1) - 1.0)/2;
        int j = i;
        if( fabs(i - j) > eps)j++;
        m = j *(j+1)/2;
        n = m - sum;
        if(!n){
            cout << j<<endl;
        }
        else {
            while(1){
                if(n % 2== 0){
                    cout << j<<endl;
                    break;
                }
                else {
                    j ++;
                    m = j * (j + 1)/2;
                    n = m - sum;
                }
            }
        }
    }
    return 0;
}