本文正體字版由OpenCC轉換
發現座標的範圍很大,而點並不是很多,首先想到了離散化的方法。然後橫向掃描每個帶狀的區間,對於每個帶狀區間,再縱向掃描其中點的個數。這種方法是最容易想到的,但是時間複雜度卻高達O(N^2logN)。關鍵在於優化每次確定帶狀區間的縱向掃描。
顯然對於確定的帶狀區間,我們掃描時只需考慮它們的縱座標。如果我們把一個縱座標爲y的點描述成兩個事件(y,1)和 (y+h+1,-1),然後把所有事件按照第一關鍵字排序,定義S[i]爲前i項事件的第二關鍵字之和,那麼Max{S[i]}就是確定的帶狀區間內高度 爲w的矩形最多覆蓋到的點數。爲什麼是這樣,我們可以想象有兩個擋板,分別是y=A-h-1(下板)和y=A(上板),從下向上移動擋板,從而確定一個矩 形。某個點的第一個事件爲(y,1),當上板A=y時,該點被覆蓋,若A繼續增大,使得A-h-1=y,該點就恰好離開了覆蓋區域,反過來我們可以以爲是 A=y+h+1,所以定義第二個事件爲(y+h+1,-1)。這樣,前i個事件的第二關鍵字和S[i],就代表了矩形在某個位置時覆蓋的點數。S[i]的 最大值就是確定的帶狀區間內最大的覆蓋點數。
帶狀區間的左右掃描,也可以考慮成兩個擋板之間的問題,首先確定擋板的初始位置在最左端,依次向右移動左右兩個擋板。確定一個區間後,統 計點事件的最大前綴和成了最關鍵的問題。由於左右擋板是移動的,我們需要動態統計一個排序結構。於是我們想到了用平衡樹,維護每個點事件的第一關鍵字(y 座標)升序,並記錄權。移動右擋板時,把右擋邊新位置所在線上的所有點對應的兩個點事件加入平衡樹;移動左擋板時,把左擋板時,把左擋邊所在線上的所有點 事件從平衡樹中刪除。
爲了快速統計出最大的前綴和,在此基礎上,我們還需要對於平衡樹中每個節點維護其子樹所有節點權值和,以及子樹中最大的前綴和。定義p的權值爲p.w,以節點p爲根的子樹的權值和爲p.s,以節點p爲根的子樹的最大的前綴和爲p.m,我們可以遞推算出p.m的值。
p.m=Max{
p.left.m; //最大前綴和的尾元素在左子樹
p.left.s+p.w; //最大前綴和的尾元素就是p
p.left.s+p.w+p.right.m; //最大前綴和的尾元素在右子樹
}
於是全部序列的最大前綴和就是根節點root.m。
於是得到的算法如下:
- 建立離散化座標系;
- 左右掃描,確定帶狀區間,維護平衡樹中節點;
- 統計對於確定帶狀區間,平衡樹中元素最大的前綴和;
/*
* Problem: POI2001 kop
* Author: Guo Jiabao
* Time: 2009.2.7 16:16
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=15001;
struct point{int x,y;};
struct linknode{int s;linknode *next;};
class Treap_node
{
public:
Treap_node *left,*right;
int fix,weight,sum,m,key;
Treap_node(int tk,int w):key(tk),weight(w),sum(w),m(w){fix=rand();left=right=0;}
inline int leftsum (){return left ?left ->sum:0;}
inline int rightsum(){return right?right->sum:0;}
};
int H,W;//區域高度 寬度
int N,L,Lc=-1,MaxAns;
int D[MAXN];
point P[MAXN];
linknode LS[MAXN],*Line[MAXN];
Treap_node *Treap_root;
void Treap_Rotate_Right(Treap_node *&p)
{
Treap_node *q=p->left;
q->sum+=p->rightsum()+p->weight;
p->sum=q->rightsum()+p->rightsum()+p->weight;
p->left=q->right;
q->right=p;
p=q;
}
void Treap_Rotate_Left(Treap_node *&p)
{
Treap_node *q=p->right;
q->sum+=p->leftsum()+p->weight;
p->sum=q->leftsum()+p->leftsum()+p->weight;
p->right=q->left;
q->left=p;
p=q;
}
void Treap_maintain(Treap_node *&p)
{
int lm,ls,rm;
lm=ls=rm=0;
if (p->left)
lm=p->left->m,ls=p->left->sum;
if (p->right)
rm=p->right->m;
p->m=lm;
if (ls + p->weight > p->m) p->m = ls + p->weight;
if (ls + p->weight + rm > p->m) p->m=ls + p->weight + rm;
}
void Treap_edit(Treap_node *&p,int v,int delta)
{
if (!p)
p=new Treap_node(v,delta);
else
{
if ( v < p->key )
{
p->sum+=delta;
Treap_edit(p->left,v,delta);
if (p->left && p->left->fix < p->fix)
{
Treap_Rotate_Right(p);
Treap_maintain(p->right);
}
Treap_maintain(p);
}
else if ( v > p->key )
{
p->sum+=delta;
Treap_edit(p->right,v,delta);
if (p->right && p->right->fix < p->fix)
{
Treap_Rotate_Left(p);
Treap_maintain(p->left);
}
Treap_maintain(p);
}
else
{
p->weight+=delta;
p->sum+=delta;
Treap_maintain(p);
}
}
}
void linktable_ins(linknode *&p,int v)
{
if (p)
{
linknode *t=p;
p=&LS[++Lc];
p->next=t;
}
else
p=&LS[++Lc];
LS[Lc].s=v;
}
void init()
{
freopen("kop.in","r",stdin);
freopen("kop.out","w",stdout);
scanf("%d%d%d",&W,&H,&N);
for (int i=1;i<=N;i++)
scanf("%d%d",&P[i].x,&P[i].y);
}
inline int cmp(const void *a,const void *b)
{
return ((point *)a)->x - ((point *)b)->x;
}
void discrete() //離散化橫座標 建立鏈表
{
int i,lastv=-1;
qsort(P+1,N,sizeof(P[0]),cmp);
L=0;
for (i=1;i<=N;i++)
{
if (P[i].x!=lastv)
{
lastv=P[i].x;
D[++L]=P[i].x;
linktable_ins(Line[L],P[i].y);
}
else
linktable_ins(Line[L],P[i].y);
}
}
void RemoveLine(int p)
{
for (linknode *k=Line[p];k;k=k->next)
{
Treap_edit(Treap_root,k->s,-1);
Treap_edit(Treap_root,k->s+H+1,1);
}
}
void AddLine(int p)
{
for (linknode *k=Line[p];k;k=k->next)
{
Treap_edit(Treap_root,k->s,1);
Treap_edit(Treap_root,k->s+H+1,-1);
}
}
void scanx() //橫向掃描 確定區間
{
int Lb,Rb;
AddLine(1);
for (Lb=Rb=1;Rb<L && Lb<=L;)
{
while (Rb+1<=L && D[Rb+1]-D[Lb]<=W)
AddLine(++Rb);
if (Treap_root->m>MaxAns)
MaxAns=Treap_root->m;
RemoveLine(Lb++);
}
}
void solve()
{
discrete();
scanx();
printf("%d",MaxAns);
}
int main()
{
init();
solve();
return 0;
}
<h2><span class="mw-headline">金礦 </span></h2>
問題描述
金礦的老師傅年底要退休了。經理爲了獎賞他的盡職盡責的工作,決定在一塊包含 n(n ≤ 15000) 個採金點的長方形土地中劃出一塊長度爲 S ,寬度爲 W 的區域獎勵給他(1 ≤ s , w ≤ 10 000)。老師傅可以自己選擇這塊地的位置,顯然其 中包含的採金點越多越好。你的任務就是計算最多能得到多少個採金點。如果一個採金點的位置在長方形的邊上,它也應當被計算在內。
輸入格式
輸入文件的第一行有兩個整數,中間用一個空格隔開,表示長方形土地的長和寬即s和w(1<=s,w<=10 000)。第二行有一個整數n(1<=n<=15 000),表示金礦數量。下面的n行與金礦相對應,每行兩個整數x和y (-30 000<=x,y<=30 000),中間用一個空格隔開,表示金礦的座標。
輸出格式
輸出文件只有一個整數,表示選擇的最大金礦的數。
輸入樣例
1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2
輸出樣例
4
上次修改時間 2017-05-22