我的代码没有达到时间限制，即使它似乎产生了正确的输出。如何减少代码运行所需的时间？

Question

问题 - 对于正整数 n 让我们定义一个函数 f： f(n)⟩=⟩-⟩1 + 2 -⟩3 +⟩..⟩+(⟩-⟩1)^n*n 您的任务是计算给定整数 n 的 f(n)。

输入- 单行包含正整数n(1 ≤ n ≤ 10^15).

输出- 在一行中打印 f(n)。

Link 提问 - https://codeforces.com/problemset/problem/486/A

我的代码-

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long t,sum=0;
    cin >> t;
    for(long long i=1;i<=t;i++){
        if(i%2!=0){
            sum = sum - i;
        }else{
            sum = sum + i;
        }
    }
    cout << sum;
}

代码似乎产生了正确的输出，但是时间限制是个问题。每次测试的时间限制为 1 秒。当输入为 1000000000000000 时，它表示超出了时间限制并且测试用例失败。如何减少我的代码花费的时间？

Answer 1

您的算法具有 O(N) 的复杂性，因此它失败了。我们可以在这里提出一个 O(1) 的解决方案。查看 f(n) 的值，以使其更容易。

f(1) = -1
f(2) = 1
f(3) = -2
f(4) = 2
f(5) = -3
f(6) = 3

这里有 2 个简单的观察结果：

n%2==0

f(n) 为正
abs(f(n)) = ceil(n/2)

利用这些事实，算法的复杂度降低到 O(1)。

Answer 2

int main()
{
    long long t,sum=0;
    cin >> t;
    if(t%2)
        sum-=((t+1)/2);
    else
        sum+=(t/2);
 
    cout << sum;
}

对于给定的奇数 'n' 和是 -(n+1)/2 对于给定的偶数 'n' 和是 (n+1)/2

你可以通过写下几个例子来找到规律。我对此进行了测试，并在 codeforces 中也接受了。时间复杂度为 O(1).

我的代码没有达到时间限制，即使它似乎产生了正确的输出。如何减少代码运行所需的时间？

My code is failing the time limit even though it seems to produce the correct output. How do I decrease the time taken for my code to work?

c++

algorithm

for-loop

if-statement

time-complexity