)
★ FEATURED ARTICLE 题目链接https://codeforces.com/gym/105911/problem/D题目大意给定三维空间内的若干条线段限制其端点在一给定长方体上求对于任意与坐标轴垂直的平面最多能和多少条线段相交。题目思路考虑垂直于x轴切一刀的情况对于一条线段从x1到x2它能被xc 切断当且仅当x1≤c≤x2。 所以问题转化为给定n条线段求最多有多少条线段覆盖同一位置。 那么我们将线段离散化考虑差分对于x1到x2把x1加上1x21 减去1然后求一遍前缀和即可。 y, z 轴同理代码如下:时间复杂度O(nlogn)#include bits/stdc.h using namespace std; #define ll long long #define endl \n struct segment { int x1, y1, z1; int x2, y2, z2; }; int maxoverlap(vectorpairint,intintervals) { if(intervals.empty()) { return 0; } //1.收集所有需要离散化的坐标点 vectorint coords; for(auto p:intervals) { coords.push_back(p.first);//L coords.push_back(p.second 1); // R1 } //2.排序去重 sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); //3.差分数组 vectorint diff(coords.size(), 0); for(auto p:intervals) { int L p.first; int R p.second; int idxL lower_bound(coords.begin(), coords.end(), L) - coords.begin(); int idxR lower_bound(coords.begin(), coords.end(), R 1) - coords.begin(); diff[idxL]; diff[idxR]--; } //4.前缀和求最大值 int cur 0; int ans 0; for(auto i:diff) { cur i; ans max(ans, cur); } return ans; } void solve() { int n, a, b, c; cin n a b c; vectorsegment segs(n); for (int i 0; i n;i) { cin segs[i].x1 segs[i].y1 segs[i].z1; cin segs[i].x2 segs[i].y2 segs[i].z2; } int ans 0; //处理x方向 vectorpairint, int intervals_x; for(auto s:segs) { int L min(s.x1, s.x2); int R max(s.x1, s.x2); intervals_x.push_back({L, R}); } ans max(ans, maxoverlap(intervals_x)); //处理y方向 vectorpairint, int intervals_y; for (auto s : segs) { int L min(s.y1, s.y2); int R max(s.y1, s.y2); intervals_y.push_back({L, R}); } ans max(ans, maxoverlap(intervals_y)); //处理z方向 vectorpairint, int intervals_z; for (auto s : segs) { int L min(s.z1, s.z2); int R max(s.z1, s.z2); intervals_z.push_back({L, R}); } ans max(ans, maxoverlap(intervals_z)); cout ans endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T 1; // cin T; while (T--) { solve(); } return 0; }map简化// https: // codeforces.com/gym/105911/problem/D #include bits/stdc.h using namespace std; #define int long long #define endl \n struct node { int x, y, z; int x1, y1, z1; }; // 对某个方向求区间覆盖最多点 // coords[i]{l,r}表示第i条线段在该方向上的区间 int f(const vectorpairint, int coords) { mapint, int diff; for (auto p : coords) { diff[p.first]; diff[p.second 1]--; } int cur 0; int ans 0; for (auto p : diff) { cur p.second; ans max(cur, ans); } return ans; } void solve() { int n, a, b, c; cin n a b c; vectornode v(n); // 每个方向存一个区间数组 vectorpairint, int xs, ys, zs; // xs[i]第i条线段在x方向上的区间[min(v[i].x, v[i].x1), max(v[i].x, v[i].x1)] for (int i 0; i n; i) { cin v[i].x v[i].y v[i].z v[i].x1 v[i].y1 v[i].z1; xs.push_back({min(v[i].x, v[i].x1), max(v[i].x, v[i].x1)}); ys.push_back({min(v[i].y, v[i].y1), max(v[i].y, v[i].y1)}); zs.push_back({min(v[i].z, v[i].z1), max(v[i].z, v[i].z1)}); } int ans 0; ans max(ans, f(xs)); ans max(ans, f(ys)); ans max(ans, f(zs)); cout ans endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T 1; // cin T; while (T--) { solve(); } return 0; }
阅读完成 · 觉得有帮助？
)
)
