POJ 1844 Sum 解题报告

 

资源来源：http://blog.chinaunix.net/u3/105033/index.html

 

一、题目描述

  为从1到N的N个自然数每个分配一个符号（+或者-），并计算这个表达式的和sum。问题是对于给定的数S，计算最少需要多少个自然数，使得可以通过分配符号给这1到N个数来得到S。（0）比如，12 = -1+2+3+4+5+6-7，则对于给定的数S=12，最少需要7个数来得到12。

二、解题思路

   假设T(S)表示输入为S时的输出结果，如T(12)=7。给定一个数S=10的话，我们就会从1开始计算累加和1+2+3+4=10，需要4个数，每个数分配的符号都是正号，这4个数之和刚好为10。4必定是最小的，因为没有分配负号,所以T(10)=4。其它的数如6=1+2+3，3=1+2都是这种情况 。但是并不是所有数是这种情况，比如11，则不行。这时我们找到一个最小数N，使得1+2+...+N>=S，这时N=5。1+2+3+4+5=15。这里d=15-11=4，d/2=2，如果把其中2的符号变为负号的话，就能得到1-2+3+4+5=11；结果就是T(11)=5。如果上面的d是个奇数的话，则d=1+2+…+N+N+1-S一定是个偶数，得到的结果便是T(S)=N+1。例如7=1+2+3-4+5，因为d=1+2+3+4-7=3是奇数，我们再加上一个5的话，d=1+2+3+4+5-7=8是偶数，d/2=4只需要把4变成负号就能满足7=1+2+3-4+5。把这个规律可以拓展到一般情况。

三、源代码

 

#include <iostream>
#include<math.h>
using namespace std;
/**//*
    描述：求连续自然数之和
    参数：i是开始的元素，j是最一个元素
    返回：返回i+(i+1)++j的值
*/
int SumFromTo(int i,int j)
{
    return (i+j)*(j-i+1)/2;
}
/**//*
    描述：获取一个最小的数N，使得1+2++N>=Sn
    参数：N保存返回的结果
    返回：如果1+2+..+N==Sn,返回true,否则返回false
*/
bool GetN(int Sn, int & N)
{
    double n=sqrt(2*Sn+0.25)-0.5;
    N=n;
    if(n==N)
        return true;
    else
        return false;
    
}
int main()
{
    int S;
    cin>>S;
    int n;
    bool b=GetN(S,n);
    if(b)
    {
        cout<<n<<endl;
    }
    else
    {
        do
        {
            n++;
        } while((SumFromTo(1,n)-S)%2!=0);
        cout<<n<<endl;
    }
    return 1;
}

四、复杂度分析
   上面那个while()最多执行两次，故复杂度为O(1)。