原題見1003

有n條船平行于x軸，已知初始時(shí)刻的位置，向平行于x軸正向或反向走。所有船速度大小一致。現(xiàn)在海哥站在x軸上，要給船拍照，角度為朝向+y方向的固定90度，可以在任意時(shí)刻、任意位置拍，問何時(shí)拍下的完整的船數(shù)量最多。

思路

對(duì)于橫坐標(biāo)為[x, y] 縱坐標(biāo)為z的船而言，海哥可以移動(dòng)的區(qū)間為[y-z, x+z]且y-z≤x+z。對(duì)于同向運(yùn)動(dòng)的船，它們?cè)谌我鈺r(shí)刻的相對(duì)位置不發(fā)生改變，則可以記錄下每個(gè)位置可見的船數(shù)量bi。得到兩個(gè)方向的bi以后，相當(dāng)于要求以某個(gè)位置為分界線，作為兩個(gè)方向bi的最大值的相交位置。故要求向左走的船的后綴最大值m0i，以及向右走的船的前綴最大值m1i，O(N)掃一遍得到max[m0i+m1i]

掃描線

輸入多個(gè)線段位置，輸出各個(gè)位置重疊的線段個(gè)數(shù)。
輸入一個(gè)線段[l,r]時(shí)，將位置s[l]++, s[r+1]–, 則統(tǒng)計(jì)如下：

b[0] = s[0]; for(int i = 1;i < maxN;i++)b[i] = b[i-1] + s[i];

離散化

由于橫坐標(biāo)的范圍在?106~106，點(diǎn)數(shù)量在2×105，因此可以將橫坐標(biāo)離散化。

附代碼

/*--------------------------------------------* File Name: 2016百度之星復(fù)賽 1003* Author: Danliwoo* Mail: Danliwoo@outlook.com* Created Time: 2016-05-29 17:18:58 --------------------------------------------*/ #include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <algorithm> #include <cmath> using namespace std; #define N 100100 struct node {int x, y;node(){}node(int x, int y): x(x), y(y) {}void pr(){printf("pr -> %d %d\n", x, y);} }p[2][N]; int a[2*N], b[2][N], tn[2], an, num[2*N], s[2][N], m[2][N]; int find(int x){int l = 0, r = an-1;while(a[l] != x){int mid = (l+r)/2;if(a[mid] == x) return mid;if(a[mid] > x) r = mid-1;else l = mid+1;}return l; } void solve(){memset(num, 0, sizeof(num));//left 后綴最大值m[0][an-1] = b[0][an-1];for(int i = an-2;i >= 0;i--)m[0][i] = max(m[0][i], b[0][i]);//right 前綴最大值m[1][0] = b[1][0];for(int i = 1;i < an;i++)m[1][i] = max(m[1][i-1], b[1][i]);int ans = 0;for(int i = 0;i < an;i++)ans = max(ans, m[0][i]+m[1][i]);printf("%d\n", ans); } int main() {int T, o = 0;scanf("%d", &T);while(T--){int n, x, y, z, d;scanf("%d", &n);memset(s, 0, sizeof(s));memset(b, 0, sizeof(b));memset(m, 0, sizeof(m));memset(a, 0, sizeof(a));tn[0] = tn[1] = an = 0;for(int i = 0;i < n;i++){scanf("%d%d%d%d", &x, &y, &z, &d);if(y-z > x+z) continue;d = (d+1)/2;p[d][tn[d]++] = node(y-z, x+z);a[an++] = y-z;a[an++] = x+z;}sort(a, a+an); //離散化unique(a, a+an);a[an] = a[an-1];for(int i = 0;i < an;i++)if(a[i] >= a[i+1]){an = i+1;break;}for(int k = 0;k < 2;k++){for(int i = 0;i < tn[k];i++){int l = find(p[k][i].x);int r = find(p[k][i].y);s[k][l]++;s[k][r+1]--;}b[k][0] = s[k][0];for(int i = 1;i <= an;i++)b[k][i] += b[k][i-1] + s[k][i];}printf("Case #%d:\n", ++o);solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2016百度之星复赛 1003 拍照 扫描线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。