题意:有一个未知大小的矩形,每次横着或者竖着剪成两块,将其中一块放入盒子里,继续对另一块进行操作,最后把剩余的也放进盒子里,现在已知盒子内的所有矩形的长和宽,问原来可能的矩形长和宽是多少(矩形没有进行旋转)
Solution
比较容易想到把所有的矩形面积和加起来就是原矩形的面积了,然后找到矩形中最大的长和最大的宽,因为剪完后把其中一块放进盒子里了,所以原来的矩形长和宽必须至少满足这两个中的一个,接下来就是模拟剪矩形的操作了,每次挑横着或者竖着剪,去掉与长或者宽相同的所有矩形直到最后一次操作后,长或者宽为0
自己写的太答辩了,这里学了一下auto关键字内联函数,熟练掌握std的人真的好厉害
void solve()
{
int n;cin>>n;
int sum=0;
int ml=0,mr=0;
for(int i=1;i<=n;i++)
{
cin>>l[i]>>r[i];
sum+=l[i]*r[i];
ml=max(ml,l[i]);
mr=max(mr,r[i]);
st1.insert({l[i],r[i]});
st2.insert({r[i],l[i]});
}
auto check=[&](int x)
{
multiset<pii>s[2];
for(int i=1;i<=n;i++)
{
s[0].insert({l[i],r[i]});
s[1].insert({r[i],l[i]});
}
int nl=x,nr=sum/x;
for(int i=0;!s[i].empty();i^=1)
{
if (s[i].rbegin()->first!=nl) return false;
while(!s[i].empty()&&s[i].rbegin()->first==nl)
{
auto it=s[i].rbegin();
int x=it->first;
int y=it->second;
s[i].erase(s[i].lower_bound({x,y}));
s[i^1].erase(s[i^1].lower_bound({y,x}));
nr-=y;
}
swap(nr, nl);
}
return nl==0;
};
set<pii>ans;
if(sum%ml==0&&check(ml))ans.insert({ml,sum/ml});
for(int i=1;i<=n;i++)swap(l[i],r[i]);//因为从宽开始所以把长宽交换一下
if(sum%mr==0&&check(mr))ans.insert({sum/mr,mr});
cout<<ans.size()<<"\n";
for(auto it:ans)
{
cout<<it.first<<" "<<it.second<<"\n";
}
}