首页 > 代码库 > luogu P2343 宝石管理系统 暴力,思维,二分
luogu P2343 宝石管理系统 暴力,思维,二分
P2343 宝石管理系统
题目描述
GY君购买了一批宝石放进了仓库。有一天GY君心血来潮，想要清点他的宝石，于是把m个宝石都取出来放进了宝石管理系统。每个宝石i都有一个珍贵值vi，他希望你能编写程序查找到从大到小第n珍贵的宝石。但是现在问题来了，他非常不小心的留了一些宝石在仓库里面，有可能要往现有的系统中添加宝石。这些宝石的个数比较少。他表示非常抱歉，但是还是希望你的系统能起作用。
输入输出格式
输入格式：第一行一个整数m，q，表示已经取出来的宝石个数以及接下来的查询或插入操作个数。
第二行m个整数，表示这m个宝石的珍贵值。
以下q行，每行两个整数c，n,
若c=1（即询问），则输出当前第n珍贵的宝石，
若c=2（即插入），则往系统中插入珍贵值为n的宝石。
输出格式：对于每个c=1（询问）,输出当前第n珍贵的宝石的珍贵值vi。
输入输出样例
输入样例#1：
5 31 3 2 5 61 32 41 6
输出样例#1：
31
Pre
好把，这题其实是zyf小盆友叫我去做的，一开始想用数组next模拟链表，结果打了个错误百出的版本交了上去，然后就WA+TLE了然后猛然意识到这题直接模拟链表的时复超高
所以开始想用树状数组来记录，然后就怂了，开始寻找其他方法……
暴力qsort一遍，然后每次加入后再qsort = 60 points
for一遍尝试找第一比他小的，可以直接插入到它前面 ，然后平移数组= 80 points
Solution
// 注意：感觉这似乎不是正解qwq
于是进入正题
首先既然我们可以直接插入加平移数组，既然可以往左平移，为啥不能往右呢？
所以我们可以在平移时加个优化判断向左平移方便还是向右平移方便
------------ubuntu上的gdb坏了，于是只能用write来debug .... 【欲哭无泪】
好,处理完后啦，还是80 points ？
于是机智的你想到了二分
没错再加上二分找第一比他小的 就AC啦原来这么水。。。
最后分析一下时间复杂度，忽略二分时间复杂度添加操作总的大概为
，查询就是
，查询就是1 program wonder; 2 var 3 n,q,i,c,x,left,right,aa,bb:longint; 4 a:array[-110000..110000] of longint; 5 6 procedure qsort(l,r:longint); //从大到小qsort 7 var i,j,m,x:longint; 8 begin 9 i:=l; j:=r; m:=a[(l+r) div 2];10 repeat11 while a[i]>m do inc(i);12 while a[j]<m do dec(j);13 if i<=j then begin14 x:=a[i];a[i]:=a[j];a[j]:=x;15 inc(i);dec(j);16 end;17 until i>j;18 if i<r then qsort(i,r);19 if j>l then qsort(l,j);20 end;21 22 procedure add;23 var24 ii,jj,m:longint;25 begin26 27 ii:=left; jj:=right;28 while ii<jj do29 begin30 m:=ii+(jj-ii) div 2;31 if a[m]>x then ii:=m+132 else jj:=m-1;33 end; //二分查找第一个比他小的34 35 for ii:=ii to right do //insert36 if x>a[ii] then37 begin38 bb:=n-ii+1; //bb为右移数组的花费39 aa:=n-bb; //aa为左移数组的花费40 inc(n); //n为元素个数 41 if bb<aa then begin42 inc(right); 43 for jj:= right downto ii+1 do a[jj]:=a[jj-1];44 a[ii]:=x;45 end46 else begin47 dec(left);48 for jj:= left to ii-2 do a[jj]:=a[jj+1];49 a[ii-1]:=x;50 end;51 break;52 end;53 end;54 55 begin56 readln(n,q);57 for i:= 1 to n do58 read(a[i]);59 60 qsort(1,n);61 62 left:=1; right:=n;63 for i:= 1 to q do64 begin65 readln(c,x);66 if c=1 then writeln(a[left+x-1]) 67 else add; 68 end;69 end.
luogu P2343 宝石管理系统 暴力,思维,二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。