现在的位置: 首页 > 综合 > 正文

1208: [HNOI2004]宠物收养所

2013年05月24日 ⁄ 综合 ⁄ 共 3223字 ⁄ 字号 评论关闭

1208: [HNOI2004]宠物收养所

1.用Treap树写:

只需要三个操作,插入,删除,查找(同时找出其前继后继);

View Code

/**************************************************************
Problem: 1208
User: 314911229
Language: C++
Result: Accepted
Time:268 ms
Memory:1732 kb
***************************************************************
*/

/**************************************************************
Problem: 1208
User: 314911229
Language: C++
Result: Accepted
Time:276 ms
Memory:1732 kb
***************************************************************
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define MOD 1000000
using namespace std;
typedef struct node
{
node *lchild, *rchild, *pf;//左孩子,右孩子
int v, pri;//值和优先值
}*Node;

const int inf = 0x7f7f7f7f;

int minx = -inf, maxx = inf;

//左旋转,返回新节点
Node Left_Rotate(Node &q)
{
Node p = q->rchild;
q->rchild = p->lchild;
if( p->lchild )
p->lchild->pf = q;
p->lchild = q;
p->pf = q->pf;
q->pf = p;
return p;
}

//右旋转
Node Right_Rotate(Node &q)
{
Node p = q->lchild; //新节点为q左孩子
q->lchild = p->rchild; //p的右孩子给q的左孩子
if( p->rchild )
p->rchild->pf = q;
p->rchild = q;// q成为p的右孩子
p->pf = q->pf;
q->pf = p;
return p;
}

Node NewNode(int t)
{
Node q = new node;
q->lchild = NULL;
q->rchild = NULL;
q->v = t;
q->pri = rand( ) % 10000;
return q;
}

Node insert( Node &p, Node &q, Node father)
{
if( p == NULL )
{
p = q;
p->pf = father;
}
else if( p->v > q->v )
{
p->lchild = insert(p->lchild, q, p);
if(p->lchild->pri < p->pri )
p = Right_Rotate(p);
}
else
{
p->rchild = insert(p->rchild, q, p);
if( p->rchild->pri < p->pri )
p = Left_Rotate(p);
}
return p;
}

//flag = 1,放回大于等于它的值,否则返回小于它的最大值
void find(Node p, int x)
{
if( p == NULL )
return;
if( p->v == x )
{
minx = x;
maxx = x;
return;
}
else if( p->v > x )
{
maxx = min(maxx, p->v);
find(p->lchild, x);
}
else
{
minx = max(minx, p->v);
find(p->rchild, x);
}
}


Node del(Node &p, int x)
{
if( p )
{
if( p->v > x )
{
p->lchild = del(p->lchild, x);
}
else if( p->v < x )
{
p->rchild = del(p->rchild, x);
//update( p );
}
else
{
if( p->rchild == NULL && p->lchild == NULL )
{
delete p;
return NULL;
}
else
{

if( p->lchild )//如果左孩子存在
{
if( p->rchild == NULL || (p->lchild->pri < p->rchild->pri ))//右孩子为空,或左孩子小于右孩子
{
p = Right_Rotate( p );
p->rchild = del(p->rchild, x);
//update( p );
}
else //左孩子大于右孩子
{
p = Left_Rotate( p );
p->lchild = del(p->lchild, x);
// update( p );
}
}
else //如果左孩子不存在
{
p = Left_Rotate( p );
p->lchild = del(p->lchild, x);
//update( p );
}

}
}
}
return p;
}

//求最小值

int main( )
{
int N, t, sum = 0, ans, a, b, num = 0;
Node root = NULL;
scanf("%d",&N);
while( N-- )
{
scanf("%d%d",&a,&b);
Node q = NewNode(b);
if( !num )
root = insert(root, q, NULL), num++, ans = a;
else if( ans == a )
root = insert(root, q, NULL), num++;
else
{
minx = -inf, maxx = inf;
find(root, b);
num--;
int t1 = abs(b - minx);
int t2 = abs(maxx - b);
if( t1 <= t2 )
{
sum += t1;
root = del(root, minx);
}
else
{
sum += t2;
root = del(root, maxx);
}
if( sum >= MOD)
sum %= MOD;

}
}
printf("%d\n", sum);
return 0;
}

2.用stl set写

View Code

/**************************************************************
Problem: 1208
User: 314911229
Language: C++
Result: Accepted
Time:224 ms
Memory:940 kb
***************************************************************
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <set>
#include <algorithm>

using namespace std;

#define MOD 1000000
set<int>p;
typedef set<int>::iterator it;

const int inf= 2239062149;
//const int inf =10 0000 0000;
int main( )
{
int N, a, b, c,sum = 0;
scanf("%d",&N);
p.insert(inf), p.insert(-inf);
while( N-- )
{
scanf("%d%d",&a,&b);
if( p.size() == 2)
p.insert(b),c = a;
else if( a == c )
p.insert(b);
else
{
it x = p.lower_bound(b);
int r = *x - b;
int l = b - *(--x);
if( l <= r )
sum += l, p.erase(x);
else
sum += r, p.erase(++x);
if( sum >= MOD )
sum %= MOD;
}
}
printf("%d\n", sum);
return 0;
}

 

抱歉!评论已关闭.