51Nod1562 玻璃切割

Problem

现在有一块玻璃，是长方形的（w 毫米× h 毫米），现在要对他进行切割。

切割的方向有两种，横向和纵向。每一次切割之后就会有若干块玻璃被分成两块更小的玻璃。在切割之后玻璃不会被移动。

现在想知道每次切割之后面积最大的一块玻璃是多少。

Solution

倒着做。

做法1:

multiset，每次删除之后维护两端最大值。

做法2:

并查集维护。

Code1

#include<cstdio>
#include<cmath>
#include<string>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
int w,h,n;
multiset<int>msh;
multiset<int>msv;
typedef multiset<int>::iterator mtpoi;
struct E{
    bool is_x;
    int t;
}e[200020];
char s[10];
int cnt1,cnt2,a[200020],b[200020];
int x;
ll ans[200020];
int main(){
    //printf("%f",log2(200000));
    scanf("%d%d%d",&h,&w,&n);
    for(int i=1;i<=n;i++){
        scanf("%s%d",s,&x);
        if(s[0]=='H'){
            e[i].is_x=true;
            a[++cnt1]=x;
            msh.insert(x);
        }
        else{
            e[i].is_x=false;
            b[++cnt2]=x;
            msv.insert(x);
            //printf("%d\n",x);
        }
        e[i].t=x;
    }
    msh.insert(0);
    msh.insert(w);
    msv.insert(0);
    msv.insert(h);
    sort(a+1,a+1+cnt1);
    sort(b+1,b+1+cnt2);
    a[cnt1+1]=w;
    b[cnt2+1]=h;
    int mxh=0,mxv=0;
    for(int i=1;i<=cnt1+1;i++){
        mxh=max(mxh,a[i]-a[i-1]);
    }
    for(int i=1;i<=cnt2+1;i++){
        mxv=max(mxv,b[i]-b[i-1]);
    }
    ans[1]=mxh;
    ans[1]*=mxv;

    for(int i=n;i>=2;i--){
        if(e[i].is_x==true){
            msh.erase(e[i].t);
            mtpoi r=msh.upper_bound(e[i].t);
            mtpoi l=r;
            l--;
            mxh=max(mxh,*r-*l);//puts("1");
        }
        else{
            msv.erase(e[i].t);
            //printf("del %d\n",e[i].t);
            mtpoi r=msv.upper_bound(e[i].t);
            mtpoi l=r;
            l--;
            mxv=max(mxv,*r-*l);
            //printf("%d %d\n",*l,*r);
        }
        ans[n-i+2]=mxh;
        ans[n-i+2]*=mxv;
    }
    for(int i=n;i>=1;i--){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

Code2

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
#define fo(d,s,t) for(int d=s;d<=t;d++)
#define fo0(d,s,t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int rd() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int w,h,n;
struct E{
    int l,r;
};
E ww[200020],hh[200020];
int wx[200020],hx[200020];
char s1[20];
int s2,cnt1,cnt2;
struct S{
    char x;
    int t;
};
S cur[200020];
ll ans=0;
ll anss[200020];
int main(){
    w=rd();h=rd();n=rd();
    //getchar();
    for(int i=1;i<=n;i++){
        s1[0]=getchar();
        s2=rd();
        //getchar();
        cur[i].x=s1[0];
        cur[i].t=s2;
        if(s1[0]=='H'){
            hx[++cnt1]=s2;
        }
        else{
            wx[++cnt2]=s2;
        }
    }
    sort(hx+1,hx+1+cnt1);
    sort(wx+1,wx+1+cnt2);
    hx[cnt1+1]=h;
    wx[cnt2+1]=w;
    int mxh=0,mxw=0;
    for(int i=1;i<=cnt1+1;i++){
        if(i<=cnt1)hh[hx[i]].l=hx[i-1];
        if(i<=cnt1)hh[hx[i]].r=hx[i+1];
        mxh=max(mxh,hx[i]-hx[i-1]);
        
    }
    for(int i=1;i<=cnt2+1;i++){
        if(i<=cnt2)ww[wx[i]].l=wx[i-1];
        if(i<=cnt2)ww[wx[i]].r=wx[i+1];
        mxw=max(mxw,wx[i]-wx[i-1]);//
    }
    for(int i=n;i>=1;i--){
        ans=mxw;
        ans*=mxh;
        anss[i]=ans;
        if(cur[i].x=='H'){
            int tmp1,tmp2;
            tmp1=hh[hh[cur[i].t].l].r=hh[cur[i].t].r;
            tmp2=hh[hh[cur[i].t].r].l=hh[cur[i].t].l;
            mxh=max(tmp1-tmp2,mxh);//printf("-%d\n",mxh);
        }
        else{
            int tmp1,tmp2;
            tmp1=ww[ww[cur[i].t].l].r=ww[cur[i].t].r;
            tmp2=ww[ww[cur[i].t].r].l=ww[cur[i].t].l;
            mxw=max(tmp1-tmp2,mxw);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%lld\n",anss[i]);
    }
    return 0;
}

51Nod1562 玻璃切割

原文：https://www.cnblogs.com/sz-wcc/p/11663935.html