Codeforces 527C Glass Carving

  vjudge 上题目链接:Glass Carving

  题目大意: 一块 w * h 的玻璃,对其进行 n 次切割,每次切割都是垂直或者水平的,输出每次切割后最大单块玻璃的面积:

  Codeforces 527C Glass Carving

  用两个 set 存储每次切割的位置,就可以比较方便的把每次切割产生和消失的长宽存下来(用个 hash 映射数组记录下对应值的长宽的数量即可,O(1) 时间维护),每次切割后剩下的最大长宽的积就是答案了:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
const int N = ; int w[N], h[N];    // 记录存在的边长的数量
set<int> sw, sh;    // 记录下所有切点的位置
set<int>::iterator i,j; void insert(set<int> &s, int *b, int p) {
s.insert(p);
i = j = s.find(p);
++j; --i;
--b[*j - *i];    // 除掉被分开的长宽
++b[p - *i];    // 新产生了两个长宽
++b[*j - p];
} int main() {
int ww,hh,n,p;
while(~scanf("%d %d %d",&ww,&hh,&n)) {
sw.clear(); sh.clear();
sw.insert(); sw.insert(ww);
sh.insert(); sh.insert(hh); memset(w, , sizeof w); w[ww]++;
memset(h, , sizeof h); h[hh]++;
int y = ww, x = hh; while(n--) {
getchar();
if(getchar() == 'H') {
scanf("%d",&p);
insert(sh, h, p);
}
else {
scanf("%d",&p);
insert(sw, w, p);
}
while(!w[y]) --y;    // 因为每次切割后最大值总是单调递减的,所以这样维护即可,如果从头到尾扫一遍的话会超时的
             while(!h[x])    --x;
printf("%I64d\n", (LL)x * y);
}
}
return ;
}

  参考了别人的思路才会做的,果然好强大,自己也好弱 Orz 。。。

上一篇:【Leetcode】33. Search in Rotated Sorted Array


下一篇:Codeforces Round #296 (Div. 2) C. Glass Carving [ set+multiset ]