首页 > 代码库 > Gym 100733J Summer Wars 题解:灵活运用扫描线的思想
Gym 100733J Summer Wars 题解:灵活运用扫描线的思想
题意:
解题思路:
首先把全部的点向右平移1000000个单位。然后那些线段位置不变,我们開始平移这些点,这样我们保证点向左移动的距离肯定是一个正数,方便处理。
这样我们仅仅要求出每一个点向左移动的距离后能够满足题目条件的集合W。然后在求出某个距离值在全部的集合中出现最多次数的就可以,这个次数即是答案。
而我们重点就是求这个集合W。假设暴力的寻找。题目数据范围为1000000,点数1000,两者相乘的复杂度显然不可行,这里我们就要运用扫描线的思想了。
我们把条线段看成是两个点:入点 和 出点
比方一条(x1,y) - (x2,y)的线段。我们在(x1,y)的位置上标记一个1。在(x2+1,y)的位置上标记一个-1,然后依照横坐标从左到右的顺序扫过这些点,事实上就是扫描线的思想了。然后在可行的范围内我们的P数组位置上+1。然后找出P中的最大值就可以。
这里在更新P数组的时候我们也不能够直接暴力更新,比方我们要更新区间[l,r]区间都+1。我们仅仅要在P[l]位置上+1,在P[r+1]的位置上-1,然后最后一起更新就可以。
代码例如以下:
#include <bits/stdc++.h> using namespace std; int N, M; pair<int, int> A[1000]; //储存点的坐标 struct event { //储存线段转化后的点,tp = 1 表示入点,tp = -1 表示出点 int x, y, tp; bool operator< (const event& other) const { return x < other.x; } }; event B[2015]; int P[2000016]; //维护答案的数组 int main() { //freopen("in.in", "r", stdin); //freopen("out.out", "w", stdout); scanf("%d%d", &N, &M); for (int i = 0; i < N; i++) { scanf("%d%d", &A[i].second, &A[i].first); //题目好坑啊,是依照y,x的顺序给的坐标 A[i].first += 1000000; } int y, x1, x2; for (int i = 0; i < M; i++) { scanf("%d%d%d", &y, &x1, &x2); B[i * 2] = (event) {x1, y, 1}; B[i * 2 + 1] = (event) {x2 + 1, y, -1}; } sort(B, B + 2 * M); //扫描前要先对线段转化的点依照横坐标进行排序 multiset<int> s; s.clear(); //s储存现在区间全部线段的纵坐标的集合 for (int i = 0; i < N; i++) { int last = -1; for (int j = 0, k; j < 2 * M; j = k) { for (k = j; k < 2 * M && B[k].x == B[j].x; k++) { if (B[k].tp == -1) s.erase(s.find(B[k].y)); else s.insert(B[k].y); } if (last != -1) P[A[i].first - B[j].x + 1]++, P[A[i].first - last + 1]--; //O(1)更新P数组 if (s.empty() || *s.begin() > A[i].second || *s.rbegin() < A[i].second) //表示现在横坐标下第i个点不能满足题意 last = -1; else last = B[j].x; //记录上次满足的横坐标 } } int ans = 0; for (int i = 1; i <= 2000015; i++) ans = max(ans, P[i] += P[i - 1]); //利用更新的信息同一时候寻找答案,即最大值 printf("%d\n", ans); return 0; }
Gym 100733J Summer Wars 题解:灵活运用扫描线的思想
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。