首页 > 代码库 > C. Glass Carving 正着做或者倒着做都可以
C. Glass Carving 正着做或者倒着做都可以
http://codeforces.com/problemset/problem/527/C
这题总体思路就是,每画一条线,然后就找到x间距的最max值和y间距的最max值,相乘就是当前的ans
那么我需要维护这样的一个数列,每次往里面添加一个元素,然后查询相邻两个元素的差值的最大值。
倒着做比较简单,首先把所有元素插上去,然后最大值直接暴力算一次。然后后来只有删除操作,这个操作只会让最大值变大。
每次删除后,检查上面和下面的新间距,和最大值比较一下就好。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; set<int> ss[2]; LL ans[200000 + 20]; struct Node { char op; int val; }node[200000 + 20]; void fuck(int id) { if (node[id].op == ‘H‘) { ss[1].erase(node[id].val); } else ss[0].erase(node[id].val); } void work() { int w, h, n; cin >> w >> h >> n; ss[0].insert(0); ss[0].insert(w); ss[1].insert(0); ss[1].insert(h); set<int> :: iterator it1, it2; for (int i = 1; i <= n; ++i) { char str[2]; int val, flag = false; scanf("%s%d", str, &val); if (str[0] == ‘H‘) { ss[1].insert(val); } else ss[0].insert(val); node[i].op = str[0]; node[i].val = val; } int mx1 = 1; // v it2 = ss[0].begin(); it2++; for (it1 = ss[0].begin(); it2 != ss[0].end(); ++it2, ++it1) { mx1 = max(mx1, *it2 - *it1); } int mx2 = -inf; it2 = ss[1].begin(); it2++; for (it1 = ss[1].begin(); it2 != ss[1].end(); ++it2, ++it1) { mx2 = max(mx2, *it2 - *it1); } ans[n] = 1LL * mx1 * mx2; // cout << mx1 << " " << mx2 << endl; fuck(n); mx1 = 1; // v it2 = ss[0].begin(); it2++; for (it1 = ss[0].begin(); it2 != ss[0].end(); ++it2, ++it1) { mx1 = max(mx1, *it2 - *it1); } mx2 = 1; it2 = ss[1].begin(); it2++; for (it1 = ss[1].begin(); it2 != ss[1].end(); ++it2, ++it1) { mx2 = max(mx2, *it2 - *it1); } for (int i = n - 1; i >= 1; --i) { if (node[i].op == ‘H‘) { it1 = ss[1].lower_bound(node[i].val); it2 = it1; it2++; mx2 = max(mx2, *it2 - *it1); it2 = it1; it1--; mx2 = max(mx2, *it2 - *it1); it1++; } else { it1 = ss[0].lower_bound(node[i].val); it2 = it1; it2++; mx1 = max(mx1, *it2 - *it1); it2 = it1; it1--; mx1 = max(mx1, *it2 - *it1); it1++; } it2 = it1; it2++; it1--; fuck(i); ans[i] = 1LL * mx1 * mx2; if (node[i].op == ‘H‘) { mx2 = max(mx2, *it2 - *it1); } else mx1 = max(mx1, *it2 - *it1); } for (int i = 1; i <= n; ++i) { cout << ans[i] << endl; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
写的很乱,因为是绝杀的。
正着也可以。
用一个multiset来维护当前拥有的差值,一开始是h
然后每添加一条边,可以找出在原数组中的上界和下界,这个差值是要删除的那个差值,然后添加新差值即可。
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; set<int> x, y; multiset<int> xx, yy; void work() { int w, h, n; cin >> w >> h >> n; x.insert(0), x.insert(w); y.insert(0), y.insert(h); xx.insert(w), yy.insert(h); for (int i = 1; i <= n; ++i) { char str[2]; int pos; cin >> str >> pos; if (str[0] == ‘H‘) { auto it1 = y.lower_bound(pos); int d1 = *it1; it1--; int d2 = *it1; auto del = yy.lower_bound(d1 - d2); yy.erase(del); yy.insert(d1 - pos); yy.insert(pos - d2); y.insert(pos); } else { auto it1 = x.lower_bound(pos); int d1 = *it1; it1--; int d2 = *it1; auto del = xx.lower_bound(d1 - d2); xx.erase(del); xx.insert(d1 - pos); xx.insert(pos - d2); x.insert(pos); } auto itx = xx.rbegin(), ity = yy.rbegin(); cout << 1LL * (*itx) * (*ity) << endl; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
C. Glass Carving 正着做或者倒着做都可以
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。