小G想做一个大蛋糕。
现在小G手上只有N块高为11的长方体小蛋糕,第i块小蛋糕的底面尺寸是Ai∗Bi。小G想用堆叠的方式将它们拼成一个大蛋糕,但要想把小蛋糕i放在另一小蛋糕j上方,必须要满足且Ai<Aj且Bi<Bj,否则成品就会非常不美观。
小G很快发现将所有原料用在一个大蛋糕里很可能是不可行的,于是她退而求其次,想要将所有的小蛋糕堆成尽量少的大蛋糕,你能告诉她该怎么做吗?(即你需要告诉小G一种可行的最优方案)
此外,为了简化问题,保证:
- 1≤Ai,Bi≤N;
- Ai互不相等;
- 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