当前位置：首页 > java >正文

7.12 卷积 | 最小生成树 prim

java 2025/7/12 12:41:19

lc1900.模拟比赛
算出两个指定选手最早和最晚能在第几轮碰到。
还是建议dfs捏

模拟比赛，找出两个特定选手（firstPlayer和secondPlayer）最早和最晚相遇的轮次。

1. 定义了一个“选手”结构体，包含两个属性a（战斗力）和b（编号），并规定按b值排序。
2. 主函数里，根据总人数n设置模拟次数（人数越多模拟次数越多）。
3. 每次模拟时：
- 给所有选手随机分配战斗力，让两个特定选手战斗力最高（确保他们能赢到最后相遇）。
- 模拟比赛：每轮让第i名和第rest+1-i名选手对决，赢的留下。
- 检查这一轮是否是两个特定选手相遇，记录最早和最晚的轮次。
4. 最后返回这两个记录的轮次。

简单说就是通过多次模拟比赛，算出两个指定选手最早和最晚能在第几轮碰到。

struct node
{
int a , b;
bool operator <(const node &p)
{
return b < p.b;
}
}player[30];

class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer)
{
srand(time(NULL));

// 根据n的大小设置模拟次数
int N;
if(n <= 10)
N = 800;
else if (n <= 20)
N = 8000;
else N = 38000;

int ans1 = 9999 , ans2 = 0 , rest , now;

while(N--)
{
// 剩余的运动员
rest = n;

// 初始化战斗力
for(int i = 1 ; i <= n ; i++)
{
player[i].a = rand() % 1075943;
player[i].b = i;
}
player[firstPlayer].a = 11000000;
player[secondPlayer].a = 10999999;

// 统计轮次
now = 1;

// 模拟比赛
while(rest > 1)
{
for(int i = 1 ; i <= rest / 2 ; i++)
{
if(player[i].a < player[rest + 1 - i].a)
player[i] = player[rest + 1 - i];

// 统计firstPlayer和secondPlayer相遇轮次的最大值和最小值
if(player[i].b == firstPlayer && player[rest + 1 - i].b == secondPlayer)
ans1 = min(ans1 , now) , ans2 = max(ans2 , now);
}
now++;
rest = (rest + 1) / 2;
sort(player + 1 , player + rest + 1);
}
}
vector<int> ans = {ans1 , ans2};
return ans;

}
};

dfs

class Solution {
bitset<1 << 15> m;
int the_max = 0, the_min = INT_MAX;

void dfs(int serial, int n, int firstPlayer, int secondPlayer) {
int mask = (n << 10) + (firstPlayer << 5) + secondPlayer;
int ff = n - firstPlayer + 1, fs = n - secondPlayer + 1;
if (ff == secondPlayer) {
the_max = max(the_max, serial);
the_min = min(the_min, serial);
return;
}
if (m[mask]) return;
m.set(mask);

int arr[] {firstPlayer, secondPlayer, ff, fs};
sort(arr, arr + 4);
int f_index = lower_bound(arr, arr + 4, firstPlayer) - arr;
int s_index = lower_bound(arr, arr + 4, secondPlayer) - arr;
for (int i = 0; i < arr[0]; ++i) {
for (int j = 0; j < arr[1] - arr[0]; ++j) {
int fi = arr[0] - 1 - i;
int fj = arr[1] - arr[0] - 1 - j;
int mid = (arr[2] - arr[1]) / 2;

int val[] { i, i + j, i + j + mid, i + j + mid + fj };

if (f_index == 0 && s_index == 1) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[1] + 2);
} else if (f_index == 2 && s_index == 3) {
dfs(serial + 1, (n + 1) / 2, val[2] + 1, val[3] + 2);
} else if (f_index == 0 && s_index == 2) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[2] + 2);
} else {
assert(f_index == 1 && s_index == 3);
dfs(serial + 1, (n + 1) / 2, val[1] + 1, val[3] + 2);
}
}
}
}

public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
dfs(1, n,firstPlayer, secondPlayer);
return { the_min, the_max };
}
};

计算两个特定选手（firstPlayer和secondPlayer）在比赛中最早和最晚相遇的轮次。

1. 用深度优先搜索（dfs）模拟比赛过程，不是真的比胜负，而是追踪两个选手的位置变化。

2. 每次递归代表一轮比赛，选手按规则配对后，胜者进入下一轮，位置会重新排列。

3. 代码通过记录状态（当前总人数、两个选手的位置）避免重复计算，高效找出两人相遇的最早和最晚轮次。

简单说，就是用递归模拟每一轮比赛，追踪两个指定选手的位置变化，最终得出他们最早和最晚能碰上的轮次。

找回自信dp

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
//初始化一个dp表
vector<int> dp(n+1,0);
//初始化
dp[0]=dp[1]=0;
//填表
for(int i=2;i<n+1;i++)
//根据状态转移方程得
dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
//一步两步当中，勇敢取小
return dp[n];

}
};

在 C++ 中， queue 可以存储 vector ，因为 queue 是一种容器适配器，它可以容纳任何符合要求的元素类型，包括标准容器（如 vector ）。

accumulate()累加求和

accumulate 是 C++ 标准库 <numeric> 里的一个实用工具，专门用来做累加求和

accumulate(vec开始位置, vec结束位置, 0);

eg.(nums.begin(),nums.end(),0)

最小成本的联通所有点

两个算法的相同点：每次都是加min 边

prim 加点法 if(未加点 && 最小边)

每次选最近的村子修路，修好再看其他村子经新路会不会更近，

kruskal 加边法 if(未连通 && 最小边)

lc1584.连接所有点

解决“连接所有点的最小费用”问题的，用Prim算法（一种求最小生成树的算法）

核心思路

把点想象成“城市”，连接点的费用是“修路成本”，目标是用最少成本把所有城市连通。

Prim算法的思路是**“贪心”**：从一个起点出发，每次选当前离已连通区域最近的新城市，把它连进来，直到所有城市连通。

代码

class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
// 定义一个极大值，代表初始“无限远”的距离
const int inf = INT_MAX;

int n = points.size();
int ans = 0;
// 标记点是否已加入“已连通区域”（城市是否已连通）
vector<bool> visited(n,false);
// 记录每个点到“已连通区域”的最小距离（每个城市到当前连通区的最低修路成本）
vector<int> dist(n,inf);
// 选第一个点当起点，它到自己的距离是0（自己和自己连通不要钱）
dist[0] = 0;

// 要把n个点都连通，循环n次（每次连一个新点）
for(int i = 0; i < n;i++){
// 找当前离“已连通区域”最近的点（找最低成本的城市）
int u = -1;
for(int j = 0;j < n;j ++){
// 没访问过，且是当前找到的距离最小的点
if(!visited[j]&&(u ==-1||dist[u] > dist[j])){
u = j; // 选中这个点
}
}
// 把这个点标记为“已连通”（加入修路计划）
visited[u] = true;

// 更新其他未连通点到“已连通区域”的最小距离
for(int j =0; j < n; j++){
if(!visited[j]){
// 计算当前点u和点j的曼哈顿距离（修路成本）
int newDist = abs(points[j][0]-points[u][0]) + abs(points[j][1]-points[u][1]);
// 如果经u连接更便宜，就更新“j到连通区的最小成本”
dist[j] = min(dist[j],newDist);
}
}
}
// 把所有“最小距离”加起来，就是总费用（总修路成本）
return accumulate(dist.begin(),dist.end(),0);
}
};

1. 初始化：选第一个点当起点，记录每个点到“已连通区”的距离（初始时只有起点自己，所以起点距离是0，其他是“无限远”）。
2. 选最近点：每次从“未连通”的点里，挑离“已连通区”最近的点，把它加入连通区。
3. 更新距离：加入新点后，重新算其他未连通点到“新连通区”的距离（因为可能经新点连接更便宜）。
4. 算总费用：把所有点到连通区的最小距离加起来，就是连通所有点的最小总费用。

就像“修路包工头”，每次选最近的村子修路，修好再看其他村子经新路会不会更近，最后把修路的钱全加起来，就是最省钱的方案～