Sol

简化一下题目：给你 $n$ 个楼房每个楼房有个宽度和一个高度，要你在这 $n$ 栋楼中选 $k$ 个然后用 $x$ 个空气将其填充为一个矩形，要求最小的 $x$。

我们简单一想，欸，贪心嘛。

怎么贪？选 $k$ 个的话宽度就是这 $k$ 个宽度的和，而高度就是这 $k$ 个中高度最大的值。那我们就只要先按这些楼房的高度排序，然后求出每个高度下最小的宽度，将两者的乘积与答案取 $min$ 就可以了。

如何维护最小值？用优先队列就可以了。

Tips

$ans$ 开大点，否则会哇。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int N = 1000001;
priority_queue<long long> q;//双端队列
int n,k,i,j,ans,s;
struct stu
{
        int x,y;
};
stu a[N];
bool cmp(stu x1, stu y1)
{
        return x1.y<y1.y;
}
signed main()
{
        cin >> n >> k;
        for (i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
        sort(a+1,a+n+1,cmp);
        for (i=1; i<=k; i++)
        {
                s+=a[i].x;
                q.push(a[i].x);
        }
        ans=1000000000000000000;
        for (i=k; i<=n; i++)
        {
                ans=min(ans,s*a[i].y);//与答案取min
                s+=a[i+1].x;//s是宽度
                q.push(a[i+1].x);
                s-=q.top();//更新宽度
                q.pop();
        }
        cout << ans;
}