计算被直线划分区域
在笛卡尔坐标系，存在区域[A,B],被不同线划分成多块小的区域，简单起见，假设这些不同线都直线并且不存在三条直线相交于一点的情况。
img
那么，如何快速计算某个时刻，在 X 坐标轴上[ A， B] 区间面积被直线划分成多少块？
A轴平行坐标Y轴，A (x=1)
B轴平行坐标Y轴, B(x = 20);
输入描述
输入采用多行输入，一行4个数据，分别表示两个坐标点，一行一条直线；
1，4，20,100 - 表两个点，点t1的坐标为（1,4），点t2坐标为（20,100）
输出描述
输出为整数，表示被输入线段划分的面积个数
示例1
输入
1,37,20,4 1,7,20,121
输出
4
备注
AB之间的线段不平行于Y轴
思路
几何题，当两条线在这一区域内不相交时，区域空间增加1，当两条线的交点在这一区域内时，空间增加2，所以我们判断交点是否在区域内即可
代码
public static void main(String[] args) { Scanner in = new Scanner(System.in); List<int[]> edges = new ArrayList<>(); int res = 1; while(in.hasNextLine()){ String inputLine = in.nextLine(); if (inputLine.isEmpty()) { break; // 如果输入为空行，退出循环 } res+=1; String[] line = inputLine.split(","); if(line[0]=="") continue; int[] nodes = new int[4]; for(int i=0;i<4;i++){ nodes[i] = Integer.parseInt(line[i]); } for(int[] edge:edges){ double x = getIntersection(nodes[0],nodes[1],nodes[2],nodes[3],edge[0],edge[1],edge[2],edge[3]); if(x<20 && x>1) res+=1; } edges.add(nodes); } System.out.println(res); } static double getIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){ double k1 = (y1-y2)/(x1-x2); double b1 = y1 - k1*x1; double k2 = (y4-y3)/(x4-x3); double b2 = y3 - k2*x3; double x = (b2-b1)/(k1-k2); return x; }
最佳面试策略
小明最近在找工作，收到了许多面试邀约，可参加的面试由interviews 数组表示，其中 interviews[i] = [startTimei, endTimei, possibilityi]，表示第 i 个面试在 startTimei 开始，endTimei 结束，面试成功的可能性是 possibilityi，该值越大，通过面试的可能性越大，由于精力限制，小明最多可以参加 k 场面试。
小明同一时间只能参加一场面试，如果要参加某场面试，必须完整参加这场面试才可能通过面试，即不能同时参加一个开始时间和另一个结束时间相同的两场面试。
请给出小明面试成功可能性的最大和。
示例1
输入
[[1,2,3],[3,4,2],[2,4,4]],2
输出
5
说明
小明参加 [1, 2, 3]， [3, 4, 2] 两场面试，面试通过可能性的和为 3 + 2 = 5
示例2
输入
[[1,2,3],[3,4,2],[2,4,6]],2
输出
6
说明
只参加面试 [2, 4, 6]，面试通过的可能性的和最大，为 6
思路
对于这道题，我们先定义dp的状态，dp[i][j]为面对i这个时间段的面试，已经面试了j次，决策后的最大可能值
先对interviews根据左端的值进行排序。
然后从后往前遍历interviews，使用二分搜索的方法算出当前面试i的下一场面试，然后我们逐次消耗面试次数，记录消耗j次面试机会的最大可能值，与进行下一次面试的值做比较，得到最终的最大值
注意，这里我们记录了dp[i+1][j]的值，就是当这个可能值 > i加上后面的面试的可能值时，会保留更大的那个可能值的结果
代码
import java.util.Arrays; public class algorithm { public static void main(String[] args) { int[][] s = { {1,2,3},{3,4,2},{2,4,6} }; System.out.println(maxValue(s,2)); } public static int maxValue(int[][] interviews,int k){ Arrays.sort(interviews,(a,b)->a[0]-b[0]); int n = interviews.length; int[][] dp = new int[n+1][k+1]; for(int i=n-1;i>=0;i--){ int l=i,r=n; while (l<r){ int mid = (l+r)>>1; if(interviews[i][1]<interviews[mid][0]) r=mid; else l=mid+1; } for(int j=0;j<=k;j++){ dp[i][j] = dp[i+1][j]; if(j>0) dp[i][j] = Math.max(dp[i][j],dp[r][j-1]+interviews[i][2]); } } return dp[0][k]; } }
星球间的最短通路
在一个遥远的银河中，有N个星球（编号从1到N），这些星球之间通过星际门进行连接。每个星际门都连接两个星球，并且可以双向通行。
每个星际门的开启需要消耗一定的能量，这个能量由星际门上的数字表示。每个星际门上的数字都是唯一的。
现在，由于某种原因，所有的星际门都处于关闭状态。作为一个探索者，你的任务是找出一种方式，开启最少的星际门，使得所有的星球都至少通过一个开启的星际门与其他星球连接。
给你一些可连接的选项 connections，其中 connections[i] = [Xi, Yi, Mi] 表示星球 Xi 和星球 Yi 之间可以开启一个星际门，并消耗 Mi 能量。
计算联通所有星球所需的最小能量消耗。如果无法联通所有星球，则输出-1。
示例1
输入
3,[[1, 2, 5], [1, 3, 6], [2, 3, 1]]
输出
6
备注
1 ≤ N ≤ 100
思路
使用kruskal （克鲁斯卡尔）算法求最小图，先将所有的边按照从小到大的顺序排序，然后通过并查集将他们组合为一个最小图
代码
import java.util.Arrays; public class Main { int[] fa; void init(int n){ fa = new int[n]; for(int i=0;i<n;i++) fa[i] = i; } int find(int x){ return x == fa[x]? x: (fa[x] = find(fa[x] )); } void union(int x,int y){ fa[find(x)] = find(y); } public int minimumCost(int n,int[][] connections){ init(20000); Arrays.sort(connections,(a,b)->a[2]-b[2]); int ans = 0; for(int[] arr:connections){ int a = arr[0],b=arr[1],w=arr[2]; if(find(a)!=find(b)){ union(a,b); ans+=w; } } return ans; } public static void main(String[] args) { Main a = new Main(); int[][] s = { {1, 2, 5}, {1, 3, 6}, {2, 3, 1} }; System.out.println(a.minimumCost(3,s)) ; } }
python
m = int(input()) map1 = [] for i in range(m): x,y,z = map(int,input().split(" ")) map1.append((x,y,z)) parent = [i for i in range(m+1)] def find(i): if parent[i] != i: return find(parent[i]) return parent[i] def union(x,y): parent[find(y)] = find(x); map1 = sorted(map1,key=lambda x:x[2]) ans = 0 for i in range(m): if find(map1[i][0]) != find(map1[i][1]): union(map1[i][0],map1[i][1]) ans += map1[i][2] print(ans)
