static void Main(string[] args)
{
int[] array = GenerateRandomArray(10); // 生成随机数组
Console.WriteLine("原始数组:");
PrintArray(array);
HeapSortAlgorithm(array); // 堆排序
Console.WriteLine("排序后的数组:");
PrintArray(array);
}
// 生成随机数组
static int[] GenerateRandomArray(int size)
{
Random random = new Random();
int[] array = new int[size];
for (int i = 0; i < size; i++)
{
array[i] = random.Next(100); // 生成0到100之间的随机数
}
return array;
}
// 打印数组
static void PrintArray(int[] array)
{
foreach (int num in array)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
// 堆排序算法
static void HeapSortAlgorithm(int[] array)
{
int n = array.Length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--)
{
Heapify(array, n, i);
}
// 从堆中提取元素，逐个放置到数组末尾，并重新构建堆
for (int i = n - 1; i > 0; i--)
{
// 将当前根节点（最大值）与数组末尾元素交换
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// 重新构建堆，只需考虑根节点
Heapify(array, i, 0);
}
}
// 通过调整节点使其符合最大堆的性质
static void Heapify(int[] array, int n, int rootIndex)
{
int largest = rootIndex; // 假设根节点最大
int leftChild = 2 * rootIndex + 1;
int rightChild = 2 * rootIndex + 2;
// 比较根节点与左子节点
if (leftChild < n && array[leftChild] > array[largest])
{
largest = leftChild;
}
// 比较根节点与右子节点
if (rightChild < n && array[rightChild] > array[largest])
{
largest = rightChild;
}
// 如果根节点不是最大值，则交换根节点和最大节点
if (largest != rootIndex)
{
int temp = array[rootIndex];
array[rootIndex] = array[largest];
array[largest] = temp;
// 递归调整交换后的子树
Heapify(array, n, largest);
}
}
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;
}
};