P7762的思路和题解

· · 题解

本蒟蒻的第二篇题解来啦

刚刚做完了这道题，看到还可以提交题解，打算开工我的第二篇题解。

这里是第一篇题解，虽然因为大佬们的题解太好太多，所以没能出现在那道题的题解栏目里，但本蒟蒻仍保留下来

如有问题，还请各位大佬们批评指出

下面进入正题

思路分析：

整体思路：

如上面的大佬所说的，因为这些矩形的中心都在坐标系的（0，0）位置上，因此我们可以把这个坐标系分成四部分，分别是左上、右上、左下、右下四个部分，然后计算其中一个部分后×4就可以得出总面积。因为本蒟蒻还不懂如何证明（毕竟我还是个小学生）所以 如果还不懂的请看图 （用的是小学的轴对称图形进行的简单证明）

单个思路：

就每个矩形而言，其四分之一的部分也是一个长方形。该长方形的长是整个矩形长的二分之一，宽是整个矩形宽的二分之一，因此我们只需要将输入的长、宽分别除以2以后再相乘就可得到整个矩形的四分之一面积。

实现思路：

我们可以将输入的矩形数据处理后（处以2后）按照长进行排序。因为长最长的矩形一定把所有矩形和它宽相同的部分全部遮盖住，因此我们只需要算这个长最长的矩形的面积和剩下的矩形宽上突出的部分的面积即可。

综上所述，本蒟蒻觉得这道题用到的方法有点像分治 （我也不确定）

程序流程：

  1. 输入数据
  2. 排序（此处建议自定义排序函数）
  3. 算出长最长的矩形的面积
  4. 处理剩余的矩形宽上突出的部分
  5. 输出结果的4倍

伪代码：

导入头文件
创建矩形存储列表（建议用pair）
bool cmp(对象a,对象b){
    如果a长不等于b长{
        返回长的排序结果（小的在前） 
    } 
    否则{ 
        返回宽的排序结果（小的在前，这样更快） 
    }

}
主函数{
    输入n
    输入每个矩形并处理（长、宽除以2）
    排序
    获取长最长的矩形面积并加到总和里 
    设定宽最大值为长最长的矩形的宽 
    倒着循环{
        如果该矩形的宽>宽最大值{
            求出突出的面积并加到总和里
            设定宽最大值为该矩形的宽 
        } 
    } 
    输出和的四倍
    完活！ 
}

AC代码（带注释）：

#include<algorithm> //非万能头，效率高 
#include<utility>
#include<iostream>
using namespace std;
pair<long long,long long>x[1000005];//矩形数据存储 
bool cmp(pair<long long,long long>a,pair<long long,long long>b){//自定义排序函数 
    if(a.first != b.first){//如果长不一样先排长 
        return a.first<b.first;//小的在前 
    }
    else{
        return a.second<b.second;//长一样排宽，小的在前 
    }

}

int main(){
    long long n,s,big;//注意数据规模，n是个数，s是和，big是宽的最大值 
    cin>>n;//输入矩形个数 
    for(long long i=0;i<n;++i){//输入每个矩形数据，记得除以二 
        cin>>x[i].first>>x[i].second;
        x[i].first/=2;
        x[i].second/=2;
    }
    sort(x,x+n,cmp);//排序 
    s=x[n-1].first*x[n-1].second;//长最长的矩形的面积 
    big=x[n-1].second;//长最长的矩形的宽赋值给宽的最大值 
    /*调试输出不要管啦~ 
    for(long long i=n-1;i>-1;i--){
        printf("%d %d %d\n",i,x[i].first,x[i].second);
    }*/
    for(long long i=n-2;i>-1;--i){//倒着遍历，注意n-2，要空开长最长的矩形 
        if(x[i].second>big){//如果该矩形的宽大于宽的最大值 
            s+=(x[i].second-big)*x[i].first;//求出该矩形突出部分，其中(x[i].second-big)是为了剔除已覆盖面积 
            big=x[i].second;//宽的最大值进行更改 
        }
    }
    cout<<s*4;//输出结果 
    return 0;//开开心心的完成啦！ 
}

看了这么多，觉得好就点个赞呗~

提示：本新手很菜，该题解没有一点效率可言，请各位大佬多多指教。

友情链接： 作者的第一篇题解 作者的洛谷成长历程 作者的主页 作者的原创内容