题解：P7371 [COCI 2018/2019 #4] Kisik

· · 题解

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