自动搬运

查看原文

来自洛谷，原作者为

	Lonely_Peak 9 月 1 日再见！ || 一只蒟蒻（⊙_⊙）|| 只有坦然面对悲欢得失，才能无悔人生。 || 欢迎加入团队76929 || 关注可回关 :-)

搬运于2025-08-24 23:16:59，当前版本为作者最后更新于2025-05-28 16:21:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有 $n$ 座大楼需要建造，每座大楼都有两个属性：高度与美观度。这些大楼都建在同一条直线上。我们需要找到一种排序的方法，使得从左往右看这些大楼，所有可见楼层的总美观度最大。

解题思路

这道题可以通过贪心法来做，我们只需要找到一种排序方法，使得总美观度最大，然后再计算总美观度即可。

为了最大化总美观度，我最开始想的是尽量让高的摩天大楼在后面，这样前面的摩天大楼较矮，后面的摩天大楼较高，可以让更多的楼层被看见。但是有个问题，要是出现像题中举出的例子中的摩天大楼，被遮挡的部分美观度较小，损失小于回报。

那么应该怎么办呢？经过思考，我猜测最优策略可能是将摩天大楼按照美观度降序排列，如果美观度相同则按高度升序排列。因为这样可以使价值大的先被看见，使得总美观度尽量大。

来通过输入输出样例验证一下：

对于样例输入#1：

• 排序后的大楼为 $(2,4)$，$(4,3)$，$(1,2)$，$(3,1)$。
• 那么总美观度就是 $4\times 2 + 2\times 3 = 14$。正确。

对于样例输入#2：

• 排序后的大楼为 $(1,8)$，$(2,6)$，$(8,5)$，$(9,4)$，$(10,3)$，$(3,2)$。
• 那么总美观度就是 $8\times 1 + 6\times 1 + 5\times 6+4\times 1+3\times1 = 51$。正确。

那么，我们的程序应该完成以下内容：

1. 将摩天大楼按照美观度降序排列。如果美观度相同，则按照高度升序排列。
2. 遍历排序后的摩天大楼，对于每个摩天大楼：如果它的高度 $h$ 大于已看到的最大高度 $maxh$，则它的可见楼层数是 $h - maxh$，美观度为 $w \times (h - maxh)$（$w$ 为当前大楼的美观度）。更新 $maxh$ 为当前摩天大楼的高度 $h$。

参考代码

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
using namespace std;
const int W = 1e5 + 5;
struct building {
	int high, vis;
} a[W];
int n, ans;
bool cmp(building x, building y) {
	if (x.vis == y.vis) return x.high < y.high;
	else return x.vis > y.vis;
} //首先按照 vis 降序排列。如果 vis 相同，则按照 high 升序排列。
signed main() {
	fast_running;
	cin >> n;
	for (Rint i = 1; i <= n; i++) cin >> a[i].high;
	for (Rint i = 1; i <= n; i++) cin >> a[i].vis;
	sort(a + 1, a + n + 1, cmp);  //使用 cmp 函数对摩天大楼进行排序。 
	int maxn = 0;
	for (Rint i = 1; i <= n; i++) {  //计算总美观度
		if (a[i].high > maxn) {
			ans += a[i].vis * (a[i].high - maxn);
			maxn = a[i].high;
		}
	}
	cout << ans << '\n';
	return 0;
}

~ 完结撒花 ~