题目描述:
BallsInTheBox
Timelimit:1sMemorylimit:32768kb
ProblemDescription
ThereareNboxesinStaginner’shouse,andwemarkthemby1,2,…,N.ThereareNi(1<=Ni<=10^4)ballsintheboxiinitially.NowStaginnerwilldosomeoperations,andhewillaskyousomesimplequestions.
Theoperationscontain:
1.Cij:takealltheballsintheboxiintotheboxjandthrowtheboxiaway,youcansurethatiisdifferentfromj.
2.Ain:addn(1<=n<=10^4)ballsintotheboxi.
3.Bin:taken(n>=0)ballsawayfromboxi,youcansurethatnisnotbiggerthanthenumberofballsintheboxi.
4.Qk:Staginneraskyouforthek-thsmallestnumberofballsinthebox,youcansurethatkisnotbiggerthanthetotalnumberofboxes.
Input:
Thereareseveraltestcases.
Thefirstlineofeachcasecontainstwointegers,N(1<=N<=10^5),M(1<=M<=10^5),indicatesthenumberofboxesandthenumberofoperations.ThenextlinecontainsNintegers,thei-thintegerindicatesthenumberofballsintheboxi.ThentherewillbeMlines,eachlinehasanoperationlikesomeoneoftheoperationsinthedescription.
Output:
Foreachtestcase,youneedonlyprintoneintegerforeachoperation“Qk”,indicatesthek-thsmallestnumberofballsinthebox.
SampleInput:
37
123
A31
C21
Q1
B34
Q1
C31
Q1
SampleOutput:
3
0
3
题目意思很简单,给定N个盒子和M个操作,然后给出初始时每个盒子里球的个数,接下来时M个操作,操作分为四种,
A a b :把编号为a的盒子里的球的数量增加b
B a b :把编号为a的盒子里的球的数量减少b
C a b :把编号为a的盒子里的球全倒进编号为b的盒子里,然后扔掉盒子a
Q k :查询球数第k小的盒子,对于每一个Q输出一行为该盒子里的球数
思路,如果用数组直接存,A B C 三个操作都容易实现,复杂度为O(1),然而Q操作每次都会花费O(n)的时间,n达到10^5,而且有10^5个询问,给定时限只有1s,肯定超时,于是想到用平衡二叉树来动态维护这些盒子,这样A B C D的时间复杂度都为O(logn),应该不会超时。
郁结的过程:比赛当时由于SBT不会写。。AVL写的不熟,然后果断放弃了该题,比赛之后弄到了题目和数据,自己在本地慢慢的搞,起初只用盒子里的球数来作为关键码,这样对于球数相同的情况是不能够处理了(经过旋转会破坏BST的性质),然后想到用盒子的球数和盒子的编号一起做关键码(球数为第一关键码,编号为第二关键码),这样就能够保证所有的关键码都不相同,于是终于AC了。 总算是把AVL写的比较熟练了。虽然代码风格比较挫。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
//关键码结点类
struct Node
{
int wgt;
int num;
Node(int w=0,int n=0):wgt(w),num(n){}
bool operator < (const Node &n) const
{
if(wgt!=n.wgt)return wgt<n.wgt;
else return num<n.num;
}
bool operator == (const Node &n) const
{
return wgt==n.wgt&&num==n.num;
}
};
//AVL树
struct AVLTree
{
int l[MAXN],r[MAXN],size[MAXN],next[MAXN],h[MAXN],ROOT;
Node Key[MAXN];
int newnode(int w,int n)
{
int node = next[0];
Key[node].wgt = w;
Key[node].num = n;
next[0] = next[node];
h[node] = size[node] = 1;
return node;
}
void delnode(int x)
{
next[x] = next[0];
next[0] = x;
Key[x].wgt = Key[x].num = h[x] = size[x] = l[x] = r[x] = 0;
}
void init()
{
for(int i=0;i<MAXN;i++)next[i]=i+1;
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(size,0,sizeof(size));
memset(h,0,sizeof(h));
ROOT = 0;
}
void left_rotate(int &p)
{
int x = r[p];
r[p] = l[x];
l[x] = p;
size[p] = size[l[p]]+size[r[p]]+1;
size[x] = size[l[x]]+size[r[x]]+1;
h[p] = max(h[l[p]],h[r[p]])+1;
h[x] = max(h[l[x]],h[r[x]])+1;
p = x;
}
void right_rotate(int &p)
{
int x = l[p];
l[p] = r[x];
r[x] = p;
size[p] = size[l[p]]+size[r[p]]+1;
size[x] = size[l[x]]+size[r[x]]+1;
h[p] = max(h[l[p]],h[r[p]])+1;
h[x] = max(h[l[x]],h[r[x]])+1;
p = x;
}
void insert(int &p,Node k)
{
if(!p)
{
p = newnode(k.wgt,k.num);
return;
}
if(k<Key[p])insert(l[p],k);
else insert(r[p],k);
h[p] = max(h[l[p]],h[r[p]])+1;
size[p] = size[l[p]]+size[r[p]]+1;
if(h[l[p]]-h[r[p]]==2)//L
{
if(h[l[l[p]]]>h[r[l[p]]])//LL
{
right_rotate(p);
}
else
{
left_rotate(l[p]);
right_rotate(p);
}
}
else if(h[l[p]]-h[r[p]]==-2)//R
{
if(h[r[r[p]]]>h[l[r[p]]])//RR
{
left_rotate(p);
}
else
{
right_rotate(r[p]);
left_rotate(p);
}
}
}
int findmin(int &p)
{
if(l[p])return findmin(l[p]);
return p;
}
void remove(int &p,Node k)
{
if(p)
{
if(k==Key[p])
{
if(!l[p])
{
int x = p;
p = r[p];
delnode(x);
}
else if(!r[p])
{
int x = p;
p = l[p];
delnode(x);
}
else
{
int x = findmin(r[p]);
Key[p] = Key[x];
remove(r[p],Key[x]);
}
}
else if(k<Key[p])remove(l[p],k);
else remove(r[p],k);
if(p)
{
h[p] = max(h[l[p]],h[r[p]])+1;
size[p] = size[l[p]]+size[r[p]]+1;
}
if(h[l[p]]-h[r[p]]==2)//L
{
if(h[l[l[p]]]>h[r[l[p]]])//LL
{
right_rotate(p);
}
else
{
left_rotate(l[p]);
right_rotate(p);
}
}
else if(h[l[p]]-h[r[p]]==-2)//R
{
if(h[r[r[p]]]>h[l[r[p]]])//RR
{
left_rotate(p);
}
else
{
right_rotate(r[p]);
left_rotate(p);
}
}
}
}
int Select(int p,int k)
{
int rank = size[l[p]]+1;
if(rank==k)return p;
else if(rank<k) return Select(r[p],k-rank);
return Select(l[p],k);
}
}avl;
int a[MAXN];
int main()
{
int n,m;
freopen("D.in","r",stdin);
freopen("DansK2.out","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
avl.init();
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)avl.insert(avl.ROOT,Node(a[i],i));
for(int i=0;i<m;i++)
{
char op[5];int x,y;
scanf("%s",op);
if(op[0]=='A')
{
scanf("%d%d",&x,&y);
avl.remove(avl.ROOT,Node(a[x],x));
a[x]+=y;
avl.insert(avl.ROOT,Node(a[x],x));
}
else if(op[0]=='B')
{
scanf("%d%d",&x,&y);
avl.remove(avl.ROOT,Node(a[x],x));
a[x]-=y;
avl.insert(avl.ROOT,Node(a[x],x));
}
else if(op[0]=='C')
{
scanf("%d%d",&x,&y);
avl.remove(avl.ROOT,Node(a[x],x));
avl.remove(avl.ROOT,Node(a[y],y));
a[y]+=a[x];
avl.insert(avl.ROOT,Node(a[y],y));
}
else
{
scanf("%d",&x);
printf("%d\n",avl.Key[avl.Select(avl.ROOT,x)].wgt);
}
}
}
return 0;
}
分享到:
相关推荐
牛耳教育XML课件牛耳教育XML课件牛耳教育XML课件牛耳教育XML课件
牛耳教育Oracle课件牛耳教育Oracle课件牛耳教育Oracle课件牛耳教育Oracle课件
牛耳特技讲师成老师上课精华课件!!!希望为各位学习嵌入式设计的学员贡献自己的资源,欢迎下载!!!
互联网最初设计是为了能提供一个通讯网络,最初的网络是给计算机专家、 工程师和科学家用来做一些交流,当时的网络一点也不友好,那时候还没有家庭 和办公计算机,任何一个人用它,无论是计算机专家,工程师还是科学...
牛耳软件教育内部测试课件,内容最详细的见解测试方面的知识,是测试工程师必备的教材
简介:牛耳微信引流软件是一款微信推广工具,本软件以官方原版为基础,通过模式方式,实现微信的开放式营销。 牛耳微信引流软件,以不修改任何原版为基础,通过100%模拟人工方式,做到批量实现手动引流。软件全自动...
这是一个java牛耳学生选课系统,对于学习java的人非常有用,希望大家多多下载。
精选题1.doc
牛耳 嵌入式 liunx 系统编程 源码 该源码包都是上课讲的实列 QQ497519822
Linux欲执安全牛耳.pdf
。。。
安博牛耳培训课程资料,针对C语言的重难点进行强化训练,对学习C语言有很大帮助
谁执全球电动汽车牛耳.pdf
飞兆半导体:继续执功率半导体牛耳.pdf
执科技金融之牛耳招商银行APP5.0.pdf
上市教育机构,安博教育,牛耳教育C++学习课件,里边附带代码,对关联容器和string算法有详细描述.
湖南省牛耳教育新校区的最优秀作品开源 班级:080707A
牛耳培训linux_app的代码和一个bbs项目源码
从java入门到编写java程序和java运行环境
make是一个重要的软件维护程序,可以根据程序文件的修改情况自动重新编译链接目标代码,以保证目标代码总是由它的最新文件组成 make根据Makefile文件所描述的规则和文件最后修改的时间来重新编译链接目标代码 make的...