题解 | #连线游戏#

解题思路

题目要求：

在圆上均匀分布 个点

连接两点形成线段

线段不能相交（端点可以相交）

求最大可能的线段数

解题分析：

对于 个点，最多可以连接的不相交线段数是

证明：

每个点最多可以连接到两个其他点（否则会相交）

总共有 个点，每条线段连接2个点

考虑到不能相交的限制，最大线段数为

代码

cpp

java

python

#include

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)

算法及复杂度

算法：数学公式

时间复杂度： - 只需要一次简单计算

空间复杂度： - 只需要常数级别的额外空间