刷题与ZZ错误记录14

CodeForces-527C Glass Carving

题面

【VJudge】 【CodeForces】

有一个w*h的矩形,每次要么横着切一刀,要么竖着切一刀,每次你都要回答切完后最大的子矩形的面积
输入三个整数w h n表示矩形的宽度和高度,以及操作的数量
接下来n行每行一个操作
要么是
H y (表示横着在y位置切一刀)
要么是
V x(表示竖着在x位置切一刀)
2 <= w, h <= 200000, 1 <= n <= 200000

总结

这道题以前做过:传送门

一:set和multset
二:将切割玻璃改成合并玻璃,从最后往前求
最大值永远在变大
每次删去一个切割你会获得一个比较长的玻璃

AC代码

#include<bits/stdc++.h>
#define MAXN 300000
using namespace std;
char caozuo[MAXN];
long long ans[MAXN];
set<int> hset,vset;
int x[MAXN],hi[MAXN],vi[MAXN],w,h,n,d,ht,vt,hmx=-1,vmx=-1;
int main(){
    scanf("%d%d%d",&w,&h,&n);
    hi[++ht]=0;vi[++vt]=0;
    for(int i=1;i<=n;i++){
        cin>>caozuo[i]>>x[i];
        if(caozuo[i]=='H'){
            hi[++ht]=x[i];
        }else{
            vi[++vt]=x[i];
        }
    }
    hi[++ht]=h;vi[++vt]=w;
    sort(hi+1,hi+1+ht);sort(vi+1,vi+1+vt);
    for(int i=1;i<ht;i++){
        hmx = max(hmx,hi[i+1]-hi[i]);
        hset.insert(hi[i]);
    }hset.insert(hi[ht]);
    for(int i=1;i<vt;i++){
        vmx = max(vmx,vi[i+1]-vi[i]);
        vset.insert(vi[i]);
    }vset.insert(vi[vt]);
    set<int>::iterator l,r,c;
    for(int i=n;i>=1;i--){
        ans[i] = (long long)(hmx) * vmx;
        if(caozuo[i]=='H'){
            l = r = c = hset.lower_bound(x[i]);
            l--;r++;
            hmx = max(hmx,*r-*l);
            hset.erase(x[i]);
        }else{
            l = r = c = vset.lower_bound(x[i]);
            l--;r++;
            vmx = max(vmx,*r-*l);
            vset.erase(x[i]);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

页面: 1 2 3 4 5 6 7

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注