小小题解

· · 题解

该题说用最少的矩形，在最少一次中，我们可以猜想它是贪心，经过推算后，我们发现可以依次自行贴矩阵，贴矩阵时，可以按照点贴，不难证明，先按照最高的点来贴（低的点贴不到该点，即贴该点一定是按该点来贴，而其他点则不一定），即设该点坐标为 (s,d)，矩阵初始时左下角为 (s,0)，右上角为 (s,d)，接下来往右扩充，再往左（倒过来也行），注意，不用按能覆盖的点的数量为顺序来覆盖，因为所以科学道理，覆盖了一边，另一边早晚也要覆盖，且用料与当前相同。在扩充时，遇到边界在向另一边扩充，直到不能扩充了为止。然后去掉所有当前被覆盖的点，重复上述过程，最后，重复了几次，答案便是几。 每一次重复时，每一次扩充，时间复杂度为 O(1)，加起来共循环 n 次，排序为 O(n\log n)，所以时间复杂度为 O(n\log n)。

code

#include<bits/stdc++.h>
using namespace std;
struct t{
    int x,y;
    int ne;
    bool s;
    int bh;
    int en;
}; 
t a[109];
t xx[109];
t yy[109];
bool xc(t a1,t a2){
    return a1.x<a2.x;
}
bool yc(t a1,t a2){
    return a1.y>a2.y;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].bh=i;
        xx[i]=yy[i]=a[i];
    }
    sort(xx+1,xx+1+n,xc);
    sort(yy+1,yy+1+n,yc);
    int aa,bb,acc;
    for(int i=1;i<=n;i++){
        if(yy[i].bh==xx[1].bh){
            aa=i;
            break;
        }
    }
    acc=aa;
    for(int i=2;i<=n;i++){//updata:这部分是可以借助 aa 数组优化的，懒得改了，优化后时间复杂度 O(n)。
        for(int j=1;j<=n;j++){
            if(yy[j].bh==xx[i].bh){
                bb=j;
                break;
            }
        }
        yy[aa].ne=bb;
        yy[bb].en=aa;
        aa=bb;
    }
    bb=aa;
    aa=acc;
    int ans;
    ans=0;//以上均为预处理，帮助下方写代码
    for(int i=1;i<=n;i++){
        if(yy[i].s){
            continue;
        }
        ans++;
        int gh;
        gh=0;
        int hg;
        hg=yy[i].y;
        int gg;
        gg=yy[i].x;

        for(int j=yy[i].ne;j&&((gh+hg*abs(yy[j].x-gg))<=m);j=yy[j].ne){

            yy[j].s=1;
            gh+=hg*abs(yy[j].x-gg);
            gg=yy[j].x;
        }
        if(gh<=m){
            gg=yy[i].x;
            for(int j=yy[i].en;j&&((gh+hg*abs(yy[j].x-gg))<=m);j=yy[j].en){
            yy[j].s=1;
            gh+=hg*abs(yy[j].x-gg);
            gg=yy[j].x;
        }   
        }
    }
    cout<<ans;
    return 0;
}