P2234 [HNOI2002] 营业额统计

题解思路

1. 对原数组排序，记录下排序前的位置。
2. 对排序后的数组构造链表。
3. 从原数组的 \(n\) 往 \(1\) 枚举，比较排序生成链表中该元素的前驱或后继与该元素差值的最小值，加入答案。
4. 在排序生成的链表中删除该元素。

正确性的疑惑

• 一开始很困惑，难道排序链表的该元素的前驱与后继能一定符合题目“该天以前某一天”的要求，都保证天数在该元素之前吗？
• 从原数组的 \(n\) 往 \(1\) 枚举，解决了该问题。
  • 第一个操作的是 \(n\) ，即最后的天数，那么其他所有数都在该天数之前，都符合
  • 操作完之后删除了 \(n\) , 操作 \(n - 1\)，显然剩下的元素也都在该天数之前。

代码实现

实现上体现了手写链表的好处。

如果用STL实现就挺麻烦。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct node
{
	int pre = 0, nxt = 0;
} b[33000];

struct data
{
	int d, rank;
	bool operator < (const data &rhs)
	{
		return (d < rhs.d) || (d == rhs.d && rank < rhs.rank);
	}
} a[33000];

void del(int x)
{
	b[b[x].pre].nxt = b[x].nxt;
	b[b[x].nxt].pre = b[x].pre;
}

int r[33000], n, ans;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].d;
		a[i].rank = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
	{
		r[a[i].rank] = i;
		b[i].pre = i - 1;
		b[i].nxt = (i == n) ? 0 : (i + 1);
	}
	for (int i = n; i; i--)
	{
		int x = r[i];
		int j, k;
		if (b[x].pre)
			j = abs(a[b[x].pre].d - a[x].d);
		else
			j = 0x7fffffff;
		if (b[x].nxt)
			k = abs(a[b[x].nxt].d - a[x].d);
		else
			k = 0x7fffffff;
		if (i != 1)
			ans += min(j, k);
		else
			ans += a[x].d;
		del(x);
		r[i] = 0;
	}
	cout << ans;
	return 0;
}