C. Glass Carving

本文主要是介绍C. Glass Carving，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题主要是 运用set和multiset

题意就是给你一个w*h大小的长方体，每次进行一个操作，然后看每次操作完之后的剩余的最大的矩形的面积

这个过程的结果在小长方形的玻璃碎片。不移动新制造的玻璃碎片。特别是,削减将每个片段的玻璃经过成更小的碎片。

意思就是碎的也不移动，不管什么时候长方体的位置都没有变，变得只是这个长方体成为了碎片

所以用set  记录被切割的位置

用 multiset 记录现在完整方块的长度与宽度，并且每一次要把切割位置的两边的相距长度从这个集合里面减掉

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 2*1e5+5;
typedef long long LL;LL w, h, n;
set <LL> st[2];
multiset <LL> mst[2];
LL solve(int t, int val) {set<LL>::const_iterator it = st[t].lower_bound(val);LL v1 = *it, v2 = *(--it);mst[t].erase(mst[t].find(v1-v2));st[t].insert(val);mst[t].insert(v1-val);mst[t].insert(val-v2);return (*mst[t].rbegin())*(*mst[t^1].rbegin());
}int main() {scanf("%I64d%I64d%I64d", &w, &h, &n);st[0].insert(0), st[0].insert(h);st[1].insert(0), st[1].insert(w);mst[0].insert(h), mst[1].insert(w);char ch;int val;for(int i = 1;i <= n; i++) {getchar();scanf("%c %d", &ch, &val);printf("%I64d\n", ch == 'H' ? solve(0, val):solve(1, val));}return 0;
}

这篇关于C. Glass Carving的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---