题解 HZOJ 284 超市卖货 C/C++

题目传送门：

超市卖货 - 题目 - Online Judge (haizeix.com)https://oj.haizeix.com/problem/284思路：

每次寻找价格最高的商品，并尝试卖掉它：

寻找未卖出商品的日期，优先锁定其保质期最后一天，若该日期已卖出则继续向前寻找

能找到未卖出商品的日期时，收入增加，标记该日期

代码实现：

为了方便地找到价格最高的商品，我们先对商品价格连带其保质期进行排序

为实现该过程，我采用线性建堆+堆排序

其他排序也行，10000 排序一轮就算再低效的排序算法也不会超时吧

就是注意在交换价格的同时还要交换保质期

代码：

#include <stdio.h>
void swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
void MaxHeap_downAdjust(int* data, int pos, int count, int* d)
{
	while (pos * 2 <= count)
	{
		int max;
		if (pos * 2 + 1 > count) max = pos * 2;
		else max = pos * 2 + (data[pos * 2] > data[pos * 2 + 1] ? 0 : 1);
		if (data[pos] >= data[max]) break;
		swap(&data[pos], &data[max]);
		swap(&d[pos], &d[max]);
		pos = max;
	}
}
void MaxHeap_build(int* arr, int arrSize, int* d)
{
	int i;
	for (i = arrSize / 2; i >= 1; i--) MaxHeap_downAdjust(arr - 1, i, arrSize, d - 1);
}
void MaxHeap_sort(int* arr, int arrSize, int* d)
{
	MaxHeap_build(arr, arrSize, d);
	int i;
	for (i = arrSize - 1; i >= 1; i--) swap(&arr[0], &arr[i]), swap(&d[0], &d[i]), MaxHeap_downAdjust(arr - 1, 1, i, d - 1);
}
int main()
{
	int n, d[10001] = { 0 }, p[10001] = { 0 }, i, day[10001] = { 0 }, money = 0, j;
	scanf("%d", &n);//day=0表示该天未售出，=1表示已售出
	for (i = 0; i < n; i++) scanf("%d%d", &p[i], &d[i]);
	MaxHeap_sort(p, n, d);
	for (i = n - 1; i >= 0; i--) for (j = d[i] - 1; j >= 0; j--) if (!day[j]) { money += p[i]; day[j] = 1; break; }
	printf("%d", money);
	return 0;
}