首页 > 其他分享 >蛋糕

蛋糕

时间:2023-05-27 15:37:00浏览次数:41  
标签:const int Bi Ai 蛋糕 id

小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;
}

 

标签:const,int,Bi,Ai,蛋糕,id
From: https://www.cnblogs.com/eggome/p/17436785.html

相关文章

  • P1837 切出最好吃的蛋糕
    #include<iostream>#include<cstring>usingnamespacestd;constintN=110;intn;ints[N][N];//二维前缀和数组intmain(){cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){int......
  • 切蛋糕
    题目描述有一个蛋糕,它是由长度是L的二进制组成的。现在需要把蛋糕切K-1刀,这样蛋糕就会被切成K份,每一份蛋糕其实就是一段连续的二进制,而且每一份蛋糕的二进制不能有前导0。小LW今年5岁了,所以她希望把每一份蛋糕的二进制转为十进制之后,都是5的幂,即可以表示成5^X,其中X是整数。求满......
  • [NOI1999] 生日蛋糕
    看题洛谷传送门(食用更佳)点击查看复杂的题目题目背景数据加强版link示例图:样例#1样例输入#11002样例输出#168ok,开始愉快的AC之旅第一步:预处理定......
  • 生日蛋糕
    #include<iostream>#include<math.h>usingnamespacestd;constintN=30,INF=1e9;intn,m;intminv[N],mins[N];//存当前层的最小体积和最小表面积intans=INF;......
  • 【YBT2023寒假Day14 A】切割蛋糕(计算几何)
    切割蛋糕题目链接:YBT2023寒假Day14A题目大意给你一个圆,圆心在原点,每次有一条直线,切掉圆中不包含原点的部分。(直线给出的部分是它在于圆两个交点形成的线段的垂直平分......
  • 20230129 T1 生日蛋糕(birth)
    生日蛋糕(birth)伤心题。。。题意\(n\)个点的树,第\(i\)个点有点权\(1\lea_i\lem\)。对于每个\(i\)满足\(1\lei\lem\),求出连通块内点权最大值为\(i\)的个......
  • java蛋糕店蛋糕商城蛋糕系统网站源码
    简介java使用ssm开发的蛋糕商城系统,用户可以注册浏览商品,加入购物车或者直接下单购买,在个人中心管理收货地址和订单,管理员也就是商家登录后台可以发布商品,上下架商品,处理......
  • 牛客小白月赛64 C-Karashi的生日蛋糕(思维)
    https://ac.nowcoder.com/acm/contest/49244/C题目大意:Karashi决定将水果摆放成n圈,第i圈必须有i个水果。一共k个人,Karashi需要把蛋糕沿半径均分成k块,任意两块蛋糕包含......
  • 不止稳定快速,看华为云CDN如何在国际云服务市场中“分蛋糕”
    互联网时代,网络的应用已十分普及,但依然存在下载慢、网络卡顿的现象。如企业业务运行过程中出现的卡顿现象导致数据延时;各校因疫情等原因网课时间长、访问应用人数过多,造成网......
  • 吃蛋糕
    题目描述Beny想要用蛋糕填饱肚子。Beny一共想吃体积为c的蛋糕,他发现有两种蛋糕可以吃,一种体积为a,一种体积为b,但两种蛋糕各有特色。Beny想知道他一共有多少种不同......