首页 > 其他分享 >2024年2月5号总结

2024年2月5号总结

时间：2024-02-05 22:55:35浏览次数：32  
标签：总结 index return int ELEMENT 2024 MinHeap data

P1194 买礼物

洛谷题目链接

解题思路

  1. 这个题目是一个最小生成树或者说是贪心的题目，在这里我们把买的东西定义成顶点，边是优惠的价格
  2. 那么我们只要把每一个顶点连接起来可以了，但要注意优惠的价格​ 可能大于A，因此我们要比较A的价格和优惠的价格谁的花费少
  3. 接下来就是最小生成树的算法了

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 501

typedef struct {
	int f;
	int t;
	int w;
}w;

w c[N * N];
int a, b;
int ans;
int f[N];
int size;
int cnt = 0;

typedef w ELEMENT;

void quickSort(ELEMENT* a, int low, int high);
void swap(ELEMENT* a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ 
int* partition(ELEMENT* a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß

int find(int x) {
	if (x != f[x]) {
		f[x] = find(f[x]);
	}

	return f[x];
}

void unionSet(int a, int b) {
	f[find(a)] = find(b);
}

bool isSameSet(int a, int b) {
	return find(a) == find(b);
}

int main(int argc, char* argv[])
{
	sc("%d%d", &a, &b);

	for (int i = 1; i <= b; i++) {
		f[i] = i;
	}

	for (int i = 0; i < b; i++) {
		for (int j = 0; j < b; j++) {
			int t;

			sc("%d", &t);

			if (!t) {
				continue;
			}
			c[size].f = i + 1;
			c[size].t = j + 1;
			c[size].w = t;
			size++;
		}
	}

	quickSort(c, 0, size - 1);

	//	for (int i = 0; i < size; i ++) {
	//		pr("%d -> %d: %d\n", c[i].f, c[i].t, c[i].w);
	//	}

	for (int i = 0; i < size && cnt < b - 1; i++) {
		if (!isSameSet(c[i].f, c[i].t)) {
			if (c[i].w < a) {
				cnt++;
				ans += c[i].w;
				unionSet(c[i].f, c[i].t);
			}
			else {
				break;
			}
		}
	}

	pr("%d", cnt == b - 1? a + ans: ans + (b - cnt) * a);

	return 0;
}

void quickSort(ELEMENT* a, int low, int high)
{
	int* p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç 

	if (low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò 
		return;
	}

	p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç 
	quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö 
	quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
	free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä 
}
void swap(ELEMENT* a, int low, int high)
{
	ELEMENT t = { 0 };

	t = a[low];
	a[low] = a[high];
	a[high] = t;
}
int* partition(ELEMENT* a, int low, int high, ELEMENT key)
{
	int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int i = low;//´ÓÍ·¿ªÊ¼±éÀú 

	while (i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä 
		if (a[i].w < key.w) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ 
			swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý 
		}
		else  if (a[i].w > key.w) {//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ 
			swap(a, r--, i);//°ÑÓұ߽çµÄÇ°Ò»¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý 
		}
		else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä 
			i++;//Ö±½Ó¼Ó1
		}
	}
	int* p = (int*)malloc(sizeof(int) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç 
	p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
	p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
	return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç 
}

P1359 租用游艇

洛谷题目链接

解题思路

  1. 这个可以用单源最短路径来解决，把出租站定义为节点，一个出租站到另一个出租站的租金定义为边
  2. 这样问题就变成了求出租站1到出租站n的最短路径问题了

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#include <limits.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 201

typedef struct a{
	int t;
	int w;
}w;

typedef w ELEMENT;

typedef struct heap {
	ELEMENT* data;//´æ·ÅÔªËصÄÊý×é 
	int size;//×îС¶ÑÖеÄÔªËظöÊý 
	int maxSize;//¶ÑÖÐ×î¶àÄܹ»ÈÝÄɵÄÔªËظöÊý 
}minHeap, * MinHeap;

MinHeap createMinHeap(int n);//´´½¨Ò»¸ö×î¶àÄܹ»ÈÝÄÉn¸öÔªËصÄ×îС¶Ñ 
int MinHeapSize(MinHeap h);//·µ»Ø×îС¶ÑµÄÔªËظöÊý 
bool isMinHeapFull(MinHeap h);//ÅжÏ×îС¶ÑÊDz»ÊÇÂúÁË 
bool addMinHeap(MinHeap h, ELEMENT item);//Íù×îС¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMinHeap(MinHeap h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MinHeapInsert(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖÃнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉϵ÷Õû£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
void MinHeapify(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖõÄÔªËرäСÁË£¬ËùÒÔÏòϵ÷Õû¶Ñ£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
bool isMinHeapEmpty(MinHeap h);//ÅжÏ×îС¶Ñ¿ÕÁËûÓÐ 
void swap(MinHeap h, int i, int j);//½»»»×îС¶ÑÖÐiºÍjλÖõÄÔªËØ 
int MinHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚijÖйæÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷ 
void freeMinHeap(MinHeap h);//ÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
ELEMENT peekMinHeap(MinHeap h);//µÃµ½×îС¶ÑÖеĶѶ¥ÔªËØ 

int n;
int head[N];
int next[N * N];
int to[N * N];
int weight[N * N];
int cnt = 1;
int t;
int dist[N];
bool v[N];

int main(int argc, char* argv[])
{
	sc("%d", &n);

	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			sc("%d", &t);

			next[cnt] = head[i + 1];
			to[cnt] = j + 2 + i;
			weight[cnt] = t;
			head[i + 1] = cnt++;
		}
	}

	/*for (int i = 1; i <= n; i++) {
		pr("%d:", i);

		for (int j = head[i]; j; j = next[j]) {
			pr("%d %d\n", to[j], weight[j]);
		}
		pr("\n");
	}*/

	for (int i = 1; i <= n; i++) {
		dist[i] = INT_MAX;
	}

	MinHeap h = createMinHeap(N * N);

	dist[1] = 0;
	ELEMENT temp1 = { 1, 0 };
	addMinHeap(h, temp1);

	while (!isMinHeapEmpty(h)) {
		temp1 = deleteMinHeap(h);

		if (!v[temp1.t]) {
			for (int i = head[temp1.t]; i; i = next[i]) {
				if (!v[to[i]] && temp1.w + weight[i] < dist[to[i]]) {
					dist[to[i]] = weight[i] + temp1.w;
					ELEMENT temp2 = { to[i], dist[to[i]] };
					addMinHeap(h, temp2);
				}
			}
			v[temp1.t] = 1;
		}
	}

	/*for (int i = 1; i <= n; i++) {
		pr("%d ", dist[i]);
	}
	pr("\n");*/

	pr("%d", dist[n]);

	return 0;
}

MinHeap createMinHeap(int n)
{
	MinHeap h = (MinHeap)malloc(sizeof(minHeap));//¿ª±ÙÒ»¸ö×îС¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ön¸ö¿Õ¼äµÄELEMENTÊý×é 
	h->size = 0;//³õʼ»¯×îС¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×îС¶ÑÄÜ´æ·Å×î´óÔªËصĸöÊýÊÇn 

	return h;//·µ»Ø×îС¶Ñ 
}
int MinHeapSize(MinHeap h)
{
	return h->size;//·µ»Ø×îС¶ÑÖеÄÔªËظöÊý 
}
bool isMinHeapFull(MinHeap h)
{
	return h->size == h->maxSize;//Èç¹û×îС¶ÑÖеÄÔªËظöÊýµÈÓÚÄܹ»ÈÝÄɵÄ×î´óÔªËظöÊý£¬ÄÇôÂúÁË 
}
bool addMinHeap(MinHeap h, ELEMENT item)
{
	if (isMinHeapFull(h)) {//Èç¹û×îС¶ÑÒѾ­ÂúÁË£¬ÄÇô¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×î϶ÑÖÐÔªËظöÊýµÄϱêÖÐ,ÒòΪԪËظöÊýµÄϱê¾ÍÊÇÒª·ÅµÄλÖà 
	MinHeapInsert(h, h->size);//ÒòΪ¸Õ¸ÕнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈöѼÌÐø±£³Ö×îС¶Ñ£¬ÄÇô¾ÍÐèÒªÏòÉϵ÷Õû¶Ñ 
	h->size++;//ÈÃ×îС¶ÑÖеÄÔªËظöÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//Èç¹û×îС¶ÑÖÐûÓÐÔªËØ£¬ÄÇô²»ÄܽøÐÐɾ³ý£¬Î¥·¨·µ»ØÒ»¸öÌض¨µÄÖµ£¬¼´ERROR 
		ELEMENT t = { 0 };

		return t;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
	swap(h, 0, --h->size);//°Ñ×îС¶ÑÖеÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËؽøÐн»»»£¬²¢ÇÒÈöÑÖÐÔªËؼõÒ»£¬ÄÇô¾Í·ÃÎʲ»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£ 
	MinHeapify(h, 0);//ϱê0λÖõÄÔªËرä´óÁË£¬ÄÇôΪÁ˼ÌÐø±£³ÖÒ»¸ö×îС¶Ñ£¬¾ÍÒªÏòϵ÷Õû 

	return ans;//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
}
void MinHeapInsert(MinHeap h, int index)//indexλÖõÄÊýÏòÉϵ÷ÕûС¸ù¶Ñ 
{
	while (MinHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûϱêindexµÄֵСÓÚËüµÄ¸¸½Úµã 
	{
		swap(h, index, (index - 1) / 2);//ϱêindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄλÖà 
	}
}
bool isMinHeapEmpty(MinHeap h)
{
	return !h->size;//Èç¹û×îС¶ÑÖеÄÔªËØÊÇ0¸ö£¬ÄÇô¾ÍÊÇ¿Õ£¬ÓÐÔªËؾͲ»ÊÇ¿Õ 
}
void swap(MinHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MinHeapify(MinHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãϱêindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓк¢×Ó 
		int lessest = left + 1 < h->size && MinHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×ÓСÓÚ×óº¢×Ó£¬ÄÇôº¢×ÓÖÐ×îСµÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó 

		lessest = MinHeapCompare(h->data[index], h->data[lessest]) ? index : lessest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×îСµÄ»¹ÒªÐ¡£¬ÄÇô×îСµÄ½Úµã¾ÍÊǸ¸½Úµã£¬²»È»×îСµÄ½Úµã¾ÍÊǺ¢×ÓÖÐ×îСµÄ½Úµã 

		if (lessest == index) {//Èç¹û×îСµÄ½ÚµãÊǸ¸½Úµã£¬ÄÇô²»ÓüÌÐøÁË£¬ÒѾ­ÊÇ×îС¶ÑÁË 
			break;
		}

		swap(h, index, lessest);//Óë×îСµÄº¢×Ó½øÐн»»» 
		index = lessest;//¸üÐÂindexϱ꣬ÒòΪ¸Õ¸Õ½»»»ÁË 
		left = 2 * index + 1;//ÖØмÆËãϱêindexµÄ×óº¢×Ó 
	}
}
int MinHeapCompare(ELEMENT a, ELEMENT b)
{
	return a.w < b.w;//Ö±½Ó½øÐÐÖµµÄ±È½Ï 
}
void freeMinHeap(MinHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×îС¶Ñ´æ·ÅÔªËصĿռä 
	free(h);//ÔÙÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//×îС¶ÑÀïÃæûÓÐÔªËØÄÇô£¬²Ù×÷Î¥·¨£¬·µ»ØÌض¨Öµ 
		ELEMENT t = { 0 };
		
		return t;
	}

	ELEMENT ans = deleteMinHeap(h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ 

	addMinHeap(h, ans);//ÔÙ·ÅÈë×îС¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂ븴Óà 

	return ans;//·µ»Ø×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
}

P1629 邮递员送信

洛谷题目链接

解题思路

  1. 去送快递是单源最短路径，但回来的时候是多源最短路径
  2. 因此我们需要一种方法来把它转换，也就是反向建图。

图片解析

 

 有了原图和反图，通过原图我们就可以得到节点1到其他所有点的最短距离，通过反图就可以得到其他所有点到节点1的最短距离。

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#include <limits.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 1001

typedef struct {
	int t;
	int d;
}p;

typedef p ELEMENT;

typedef struct heap {
	ELEMENT* data;//´æ·ÅÔªËصÄÊý×é 
	int size;//×îС¶ÑÖеÄÔªËظöÊý 
	int maxSize;//¶ÑÖÐ×î¶àÄܹ»ÈÝÄɵÄÔªËظöÊý 
}minHeap, * MinHeap;

MinHeap createMinHeap(int n);//´´½¨Ò»¸ö×î¶àÄܹ»ÈÝÄÉn¸öÔªËصÄ×îС¶Ñ 
int MinHeapSize(MinHeap h);//·µ»Ø×îС¶ÑµÄÔªËظöÊý 
bool isMinHeapFull(MinHeap h);//ÅжÏ×îС¶ÑÊDz»ÊÇÂúÁË 
bool addMinHeap(MinHeap h, ELEMENT item);//Íù×îС¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMinHeap(MinHeap h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MinHeapInsert(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖÃнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉϵ÷Õû£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
void MinHeapify(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖõÄÔªËرäСÁË£¬ËùÒÔÏòϵ÷Õû¶Ñ£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
bool isMinHeapEmpty(MinHeap h);//ÅжÏ×îС¶Ñ¿ÕÁËûÓÐ 
void swap(MinHeap h, int i, int j);//½»»»×îС¶ÑÖÐiºÍjλÖõÄÔªËØ 
int MinHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚijÖйæÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷ 
void freeMinHeap(MinHeap h);//ÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
ELEMENT peekMinHeap(MinHeap h);//µÃµ½×îС¶ÑÖеĶѶ¥ÔªËØ 

int n, m;
int b[3];
int head1[N];
int to1[N * 100];
int w1[N * 100];
int next1[N * 100];
int cnt1 = 1;

int head2[N];
int to2[N * 100];
int w2[N * 100];
int next2[N * 100];
int cnt2 = 1;

bool v[N];
int dist[N];
ll ans;

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &m);

	for (int i = 0; i < m; i++) {
		sc("%d%d%d", b, b + 1, b + 2);

		next1[cnt1] = head1[b[0]];
		to1[cnt1] = b[1];
		w1[cnt1] = b[2];
		head1[b[0]] = cnt1++;

		next2[cnt2] = head2[b[1]];
		to2[cnt2] = b[0];
		w2[cnt2] = b[2];
		head2[b[1]] = cnt2++;
	}

	for (int i = 1; i <= n; i++) {
		dist[i] = INT_MAX;
	}

	dist[1] = 0;

	ELEMENT t = { 1, 0 };
	MinHeap h = createMinHeap(m);

	addMinHeap(h, t);

	while (!isMinHeapEmpty(h)) {
		t = deleteMinHeap(h);

		if (!v[t.t]) {
			for (int i = head1[t.t]; i; i = next1[i]) {
				if (!v[to1[i]] && w1[i] + t.d < dist[to1[i]]) {
					dist[to1[i]] = w1[i] + t.d;
					ELEMENT temp = { to1[i], dist[to1[i]] };
					addMinHeap(h, temp);
				}
			}
			v[t.t] = 1;
		}
	}
	 
	for (int i = 1; i <= n; i++) {
		ans += dist[i];
	}

	for (int i = 1; i <= n; i++) {
		dist[i] = INT_MAX;
		v[i] = 0;
	}

	dist[1] = 0;

	t.t = 1;
	t.d = 0;
	h = createMinHeap(m);

	addMinHeap(h, t);

	while (!isMinHeapEmpty(h)) {
		t = deleteMinHeap(h);

		if (!v[t.t]) {
			for (int i = head2[t.t]; i; i = next2[i]) {
				if (!v[to2[i]] && w2[i] + t.d < dist[to2[i]]) {
					dist[to2[i]] = w2[i] + t.d;
					ELEMENT temp = { to2[i], dist[to2[i]] };
					addMinHeap(h, temp);
				}
			}
			v[t.t] = 1;
		}
	}

	for (int i = 1; i <= n; i++) {
		ans += dist[i];
	}

	pr("%d", ans);

	return 0;
}

MinHeap createMinHeap(int n)
{
	MinHeap h = (MinHeap)malloc(sizeof(minHeap));//¿ª±ÙÒ»¸ö×îС¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ön¸ö¿Õ¼äµÄELEMENTÊý×é 
	h->size = 0;//³õʼ»¯×îС¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×îС¶ÑÄÜ´æ·Å×î´óÔªËصĸöÊýÊÇn 

	return h;//·µ»Ø×îС¶Ñ 
}
int MinHeapSize(MinHeap h)
{
	return h->size;//·µ»Ø×îС¶ÑÖеÄÔªËظöÊý 
}
bool isMinHeapFull(MinHeap h)
{
	return h->size == h->maxSize;//Èç¹û×îС¶ÑÖеÄÔªËظöÊýµÈÓÚÄܹ»ÈÝÄɵÄ×î´óÔªËظöÊý£¬ÄÇôÂúÁË 
}
bool addMinHeap(MinHeap h, ELEMENT item)
{
	if (isMinHeapFull(h)) {//Èç¹û×îС¶ÑÒѾ­ÂúÁË£¬ÄÇô¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×î϶ÑÖÐÔªËظöÊýµÄϱêÖÐ,ÒòΪԪËظöÊýµÄϱê¾ÍÊÇÒª·ÅµÄλÖà 
	MinHeapInsert(h, h->size);//ÒòΪ¸Õ¸ÕнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈöѼÌÐø±£³Ö×îС¶Ñ£¬ÄÇô¾ÍÐèÒªÏòÉϵ÷Õû¶Ñ 
	h->size++;//ÈÃ×îС¶ÑÖеÄÔªËظöÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//Èç¹û×îС¶ÑÖÐûÓÐÔªËØ£¬ÄÇô²»ÄܽøÐÐɾ³ý£¬Î¥·¨·µ»ØÒ»¸öÌض¨µÄÖµ£¬¼´ERROR 
		ELEMENT t = { 0 };

		return t;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
	swap(h, 0, --h->size);//°Ñ×îС¶ÑÖеÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËؽøÐн»»»£¬²¢ÇÒÈöÑÖÐÔªËؼõÒ»£¬ÄÇô¾Í·ÃÎʲ»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£ 
	MinHeapify(h, 0);//ϱê0λÖõÄÔªËرä´óÁË£¬ÄÇôΪÁ˼ÌÐø±£³ÖÒ»¸ö×îС¶Ñ£¬¾ÍÒªÏòϵ÷Õû 

	return ans;//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
}
void MinHeapInsert(MinHeap h, int index)//indexλÖõÄÊýÏòÉϵ÷ÕûС¸ù¶Ñ 
{
	while (MinHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûϱêindexµÄֵСÓÚËüµÄ¸¸½Úµã 
	{
		swap(h, index, (index - 1) / 2);//ϱêindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄλÖà 
	}
}
bool isMinHeapEmpty(MinHeap h)
{
	return !h->size;//Èç¹û×îС¶ÑÖеÄÔªËØÊÇ0¸ö£¬ÄÇô¾ÍÊÇ¿Õ£¬ÓÐÔªËؾͲ»ÊÇ¿Õ 
}
void swap(MinHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MinHeapify(MinHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãϱêindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓк¢×Ó 
		int lessest = left + 1 < h->size && MinHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×ÓСÓÚ×óº¢×Ó£¬ÄÇôº¢×ÓÖÐ×îСµÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó 

		lessest = MinHeapCompare(h->data[index], h->data[lessest]) ? index : lessest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×îСµÄ»¹ÒªÐ¡£¬ÄÇô×îСµÄ½Úµã¾ÍÊǸ¸½Úµã£¬²»È»×îСµÄ½Úµã¾ÍÊǺ¢×ÓÖÐ×îСµÄ½Úµã 

		if (lessest == index) {//Èç¹û×îСµÄ½ÚµãÊǸ¸½Úµã£¬ÄÇô²»ÓüÌÐøÁË£¬ÒѾ­ÊÇ×îС¶ÑÁË 
			break;
		}

		swap(h, index, lessest);//Óë×îСµÄº¢×Ó½øÐн»»» 
		index = lessest;//¸üÐÂindexϱ꣬ÒòΪ¸Õ¸Õ½»»»ÁË 
		left = 2 * index + 1;//ÖØмÆËãϱêindexµÄ×óº¢×Ó 
	}
}
int MinHeapCompare(ELEMENT a, ELEMENT b)
{
	return a.d < b.d;//Ö±½Ó½øÐÐÖµµÄ±È½Ï 
}
void freeMinHeap(MinHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×îС¶Ñ´æ·ÅÔªËصĿռä 
	free(h);//ÔÙÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//×îС¶ÑÀïÃæûÓÐÔªËØÄÇô£¬²Ù×÷Î¥·¨£¬·µ»ØÌض¨Öµ 
		ELEMENT t = { 0 };

		return t;
	}

	ELEMENT ans = deleteMinHeap(h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ 

	addMinHeap(h, ans);//ÔÙ·ÅÈë×îС¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂ븴Óà 

	return ans;//·µ»Ø×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
}

 

标签：总结,index,return,int,ELEMENT,2024,MinHeap,data
From： https://www.cnblogs.com/lwj1239/p/18008878

相关文章

  • WC2024 水镜
    洛谷传送门WC2024被打爆了，呜呜。我赛时会这题\(8\)分指数级暴力，哈哈。真不知道自己在干嘛。下文令\(T=2L\)。考虑如何判定一个序列\(a\)是否合法。考虑先枚举一个\(T\)。因为要求\(r_i<r_{i+1}\)，考虑讨论相邻两项的取值：若\(a_i<a_{i+1}\)则\(r_i=a_i,......
  • WC2024 游记
    2月1日测试开场读三道题，题好长！T1看起来是数数，T2是神秘构造，T3还是数数。开赛后15分钟开始想T1。直接做好像不太可做啊，然后立刻想到了拆贡献看看。发现拆贡献后问题变成了背包问题，可以\(\mathcalO(nT)\)解决。看完数据范围有点惊讶，我的做法能拿满分！在去年，金牌分数线不......
  • 洛谷 P10145 [WC/CTS2024] 线段树 题解--zhengjun
    提供一种考场做法，在思路上和官方题解的差异蛮大的，虽然结果差不多。首先需要发现\([l,r)\)区间可以算出来的充要条件是：如果对于每个选中的节点\(u\)，连无向边\((L_u,R_u)\)，则当且仅当\(l\)和\(r\)连通时区间\([l,r)\)可以算出来。证明的话，用前缀和理解这些东西，分别考虑......
  • 2024牛客寒假集训营第二场
    总的来说，这一场还是很不错的，但是还是有做的不好的地方，比方说靠别人给了D的思路，还有思维的太慢。不过继续努力吧！A.TokitsukazeandBracelet思路：签到题，直接按着题目的意思模拟就可以了。code：点击查看代码#include<bits/stdc++.h>usingnamespace......
  • 2024初三寒假年前集训测试3
    2024初三年前集训测试3ps：也不知道我为什么没写测试1，2的题解T1夕景昨日\(100pts\)题目描述\(Shintaro\)制作了\(n\)个开关，每个开关的状态可被设置为\(+\)或\(-\)。现在你有一个数列$A=(a_1,a_2,\dots,a_n)$，和一个初始值为\(0\)的变量\(v\)。你可以自由地操......
  • 每日总结
    Scala是ScalableLanguage的简写，是一门多范式的编程语言联邦理工学院洛桑（EPFL）的MartinOdersky于2001年基于Funnel的工作开始设计Scala。Funnel是把函数式编程思想和Petri网相结合的一种编程语言。Odersky先前的工作是GenericJava和javac（SunJava编译器）。Java平台的Scala于......
  • 协同办公的2024开年大战，打的就是“超级助理”
    文|智能相对论作者|沈浪开年，腾讯发布了一份报告《影响2024年的十大科技应用趋势》。其中提到，从大脑到Agent，大模型从CoPilot副驾，走向主驾驶。在不久的将来，任何上网的人都将能够拥有由人工智能驱动的个人助手，远超今天的技术水平。这一趋势，或许并不遥远。尽管腾讯旗下的企业微信还没有......
  • 耗时一个月我问遍了身边的大佬，零基础自学Java的路线，适用程序员入门&进阶，Java学习路线，2
    作为一个有志于成为Java程序员的你，或许正处在技术生涯的起点，或许已经走过了入门的道路，期待跨越进阶的门槛？无论处于哪个阶段，一条明确的学习路线都至关重要，通过向众多行业大佬请教、反复探索和实践，总结出一套适用于零基础自学者大学四年Java学习路线，也同样适用于从初级到研发专家的学......
  • 2024.2.5寒假每日总结27
    LeetCode跳跃游戏VI1696.跳跃游戏VI-力扣（LeetCode）题目描述给你一个下标从0开始的整数数组nums和一个整数k。一开始你在下标0处。每一步，你最多可以往前跳k步，但你不能跳出数组的边界。也就是说，你可以从下标i跳到[i+1，min(n-1,i+k)]包含两个端点的任......
  • 杂记 2024-02-05 农历腊月26，星期一
    1.java继承时，子类Override父类方法的限制：从这里抄的https://www.cnblogs.com/aademeng/articles/11230526.html遵循的规则：【1】访问修饰符的限制一定要不小于被重写方法的访问修饰符比如：Object类有个toString()方法，开始重写这个方法的时候我们总容易忘记Public修饰符，出错的原因......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99