题解 | #连线游戏#
连线游戏
https://www.nowcoder.com/practice/f96f4b55c1c44636a41d1eb2b04ee202
解题思路
-
题目要求：
- 在圆上均匀分布
个点
- 连接两点形成线段
- 线段不能相交（端点可以相交）
- 求最大可能的线段数
- 在圆上均匀分布
-
解题分析：
- 对于
- 证明：
- 每个点最多可以连接到两个其他点（否则会相交）
- 总共有
- 考虑到不能相交的限制，最大线段数为
- 对于
代码
#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)
算法及复杂度
- 算法：数学公式
- 时间复杂度：
- 只需要一次简单计算
- 空间复杂度：
投递字节跳动等公司8个岗位
