解题思路

  1. 题目要求：

    • 在圆上均匀分布 个点
    • 连接两点形成线段
    • 线段不能相交（端点可以相交）
    • 求最大可能的线段数

  2. 解题分析：

    • 对于 个点，最多可以连接的不相交线段数是
    • 证明：
      1. 每个点最多可以连接到两个其他点（否则会相交）
      2. 总共有 个点，每条线段连接2个点
      3. 考虑到不能相交的限制，最大线段数为

代码

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    // 最大线段数为2n-3
    cout << 2 * n - 3 << 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();
        // 最大线段数为2n-3
        System.out.println(2 * n - 3);
    }
}

n = int(input())
# 最大线段数为2n-3
print(2 * n - 3)

算法及复杂度

  • 算法：数学公式
  • 时间复杂度： - 只需要一次简单计算
  • 空间复杂度： - 只需要常数级别的额外空间