题目链接

牛牛学数列

题目描述

牛牛需要计算一个特殊数列的前 n 项之和：S(n) = 1 - 2 + 3 - 4 + ... + (-1)^(n+1) * n。

输入描述: 输入一个正整数 n (1 ≤ n ≤ 10^9)。

输出描述: 输出一个整数，表示数列的和。

解题思路

这道题要求计算一个交错级数的和。我们可以从两种角度来思考：直接模拟和数学归纳。

思路一：直接循环 (Brute Force)

最直观的方法就是按照题目的描述，写一个循环从 1 到 n。在循环中，判断当前的数字是奇数还是偶数：

  • 如果是奇数，就加到总和上。
  • 如果是偶数，就从总和中减去。

这个方法思路简单，易于实现。但题目的 n 最大可以到 10^9，直接循环 n 次会导致超时（TLE, Time Limit Exceeded），因此我们需要寻找更高效的方法。

思路二：寻找数学规律 (O(1) Solution)

让我们把数列的项两两分组，观察一下： S(n) = (1 - 2) + (3 - 4) + (5 - 6) + ...

每一对 (i - (i+1)) 的结果都是 -1。

接下来，我们根据 n 的奇偶性进行讨论：

  1. 当 n 是偶数时： 数列可以被完美地分成 n / 2 组。 例如 S(4) = (1 - 2) + (3 - 4)，共有 4 / 2 = 2 组。 每一组的和都是 -1。 所以总和就是 (n / 2) * (-1) = -n / 2。

  2. 当 n 是奇数时： 数列的前 n-1 项可以被完美地分成 (n - 1) / 2 组，最后一项 n 单独剩下。 例如 S(5) = (1 - 2) + (3 - 4) + 5。 前 (5 - 1) / 2 = 2 组的和是 2 * (-1) = -2。 再加上最后一项 n，总和就是 -(n - 1) / 2 + n。 化简一下： (-n + 1 + 2n) / 2 = (n + 1) / 2。

结论：

  • 如果 n 是偶数，S(n) = -n / 2。
  • 如果 n 是奇数，S(n) = (n + 1) / 2。

这个方法不需要循环，只需要一次判断和一次计算，时间复杂度为 O(1)，可以轻松处理 n 高达 10^9 的情况。

代码

#include <iostream>

using namespace std;

int main() {
    long long n; // n 最大 10^9，结果可能超出 int
    cin >> n;
    
    long long sum;
    if (n % 2 == 0) {
        // n 是偶数
        sum = -n / 2;
    } else {
        // n 是奇数
        sum = (n + 1) / 2;
    }
    
    cout << sum << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); // 使用 long 以免 n*n 溢出
        
        long sum;
        if (n % 2 == 0) {
            // n 是偶数
            sum = -n / 2;
        } else {
            // n 是奇数
            sum = (n + 1) / 2;
        }
        
        System.out.println(sum);
    }
}

# 读取输入的n
n = int(input())

# 根据n的奇偶性直接计算
if n % 2 == 0:
    # n是偶数
    total_sum = -n // 2
else:
    # n是奇数
    total_sum = (n + 1) // 2

print(total_sum)

算法及复杂度

  • 算法：数学规律 / 分类讨论。
  • 时间复杂度：，因为代码只包含一次条件判断和一次算术运算，与 n 的大小无关。
  • 空间复杂度：，只使用了常数级别的额外空间。