526互联

蛋糕

发布时间 2023-05-27 15:16:43作者: eggome

小G想做一个大蛋糕。

现在小G手上只有N块高为11的长方体小蛋糕，第i块小蛋糕的底面尺寸是Ai​∗Bi​。小G想用堆叠的方式将它们拼成一个大蛋糕，但要想把小蛋糕i放在另一小蛋糕j上方，必须要满足且Ai​<Aj​且Bi​<Bj​，否则成品就会非常不美观。

小G很快发现将所有原料用在一个大蛋糕里很可能是不可行的，于是她退而求其次，想要将所有的小蛋糕堆成尽量少的大蛋糕，你能告诉她该怎么做吗？(即你需要告诉小G一种可行的最优方案)

此外，为了简化问题，保证：

  1. 1≤Ai​,Bi​≤N；
  2. Ai互不相等；
  3. Bi互不相等。

把Ai当做时间，从大到小排序后逐步贪心加Bi。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
struct cake
{
    int a,b,id;
}c[N];
bool cmp(const cake& a,const cake& b)
{
    return a.a>b.a;
}
set<pair<int,int>> s;
int ans1,ans2[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>c[i].a>>c[i].b;
        c[i].id=i;
    }
    sort(c,c+n,cmp);
    for(int i=0;i<n;++i)
    {
        auto it=s.upper_bound({c[i].b,0});
        if(it==s.end())    s.insert({c[i].b,ans2[c[i].id]=++ans1});
        else
        {
            pair<int,int> tp(c[i].b,it->second);
            ans2[c[i].id]=it->second;
            s.erase(it);
            s.insert(tp);
        }
    }
    cout<<ans1<<'\n';
    for(int i=0;i<n;++i)    cout<<ans2[i]<<' ';
    return 0;
}