自动搬运

查看原文

来自洛谷，原作者为

	elainya_stars elainya_qwq

搬运于2025-08-24 22:29:14，当前版本为作者最后更新于2025-07-14 15:30:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P7371 [COCI 2018/2019 #4] Kisik

思路

读懂题后可以发现，玻璃罩的高度是每栋楼的高度的最大值，而宽度是所有楼的宽度的和，所以我们要尽量控制选择的楼的宽度，给玻璃罩“减肥”。

实现

由于我们要控制宽度，所以我们尽量用“瘦”的楼替换“胖”的楼。考虑把楼从低到高排序。排好序后先选择前 $k$ 栋楼（最矮的），再从 $k+1$ 遍历到 $n$，尝试用高楼替换原先选择的楼里最宽的，最后在每次替换所得的面积里取最小值。

由于 $1 \le K \le N \le 10^6$，我们要很快地找出原先选择的楼里最宽的，考虑优先队列。把原先选择的楼放进大根堆，第一个元素就是最宽的。

总时间复杂度为 $O(n \log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long // 不开龙龙见祖宗

const int N=1e6+5;
int n,k;
struct pp
{
	int w,h;
	bool friend operator<(pp x,pp y) {return x.h<y.h;} // 按高度排序
}a[N];

signed main()
{
	printf("ctj sb");
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	  scanf("%lld%lld",&a[i].w,&a[i].h);
	sort(a+1,a+n+1);
	priority_queue<int> w; // 优先队列储存宽度
	int tw=0,th=a[k].h; // 当前的玻璃罩宽度w+高度h
	for(int i=1;i<=k;i++)
	  tw+=a[i].w,w.push(a[i].w); // 先选择最宽的，后续慢慢替换
	int ans=tw*th; // 记录当前答案，后面取最小值
	for(int i=k+1;i<=n;i++)
	{
		tw=tw-w.top()+a[i].w; // 删掉最宽的，加上更高的楼的宽度
		w.pop();
		w.push(a[i].w); // 别忘了优先队列加上更高的楼的宽度
		th=a[i].h; // 玻璃罩高度取最高，因为排过序
		ans=min(ans,tw*th); // 答案取最小值
	}
	return !printf("%lld\n",ans);
}

给我赞赞qwq