TYVJP1038忠诚 www.tyvj.cn

忠诚[描述 Description]老管家是一个聪明能干的人。他为财主工作了整整10年,财主为了让自已账目更加清楚。要求管家每天记k次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每次的账目按1,2,3…编号,然后不定时的问管家问题,问题是这样的:在a到b号账中最少的一笔是多少?为了让管家没时间作假他总是一次问多个问题。[输入格式 Input Format]输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题,n<=100000.第二行为m个数,分别是账目的钱数.后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。[输出格式 Output Format ]输出文件中为每个问题的答案。具体查看样例。[样例输入 Sample Input]10 31 2 3 4 5 6 7 8 9 102 73 91 10[样例输出 Sample Output]2 3 1
--------------华丽的分割线--------------------------------------------------------------------刚看到这道题目,我暗笑是个水题。一个简单的思路冒了出来:分别对每段询问的排序,然后找到最小的点输出。这就需要Qsort了。可是回头看看数据范围,100000的数目这样是万万不能的。但是我还是冒着试试看的心情(希望数据很水的说)用这种方法交了一遍,WA,原因很简单:超时。看到这个题目的讨论区,大牛们都喊着要用线段树写。没错,这个题目线段树是正解,可是我想到了一个用Qsort就能过的方法如下(暗自庆幸ing..)。思路是这样的:1.可以先定义一个记录类型,在读入第二行数据时记录一下数据的位置Type datatype=record s,wz:longint;//wz是数据的位置,s是记录读入数据 end;Var a:array[1..100000]of datatype;就拿题目样例数据来说,那么 a[1].s=1,a[1].wz=1;2.好了,下一步就是Qsort(注意排序的时候比较a[i].s,交换时注意把a[i].wz和a[i].s都交换);举例来说,如果第二行数据为 1 3 2 5 4,排序之前为 i a[i].s a[i].wz 1 1 1 2 3 2 3 2 3 4 5 4 5 4 5 排序之后为 i a[i].s a[i].wz 1 1 1 2 2 3 3 3 2 4 4 5 5 5 43.排序之后再读入n行的询问起始点x,y 因为排序是升序排的,而我们寻找最少的一笔,所以用一个for循环寻找排序完成的数组中第一个位置处于[x,y]范围的,就记录为此次询问的结果(c[i]是记录结果的数组,也可以不用这个数组直接输出) k:=0; fori:=1 to n do begin readln(x,y); for j:=1to m do if(a[j].wz>=x)and(a[j].wz<=y)then begininc(k);c[k]:=a[j].s;break;end;//这里一定注意break,我们是寻找的最少的一笔, Qsort是从小到大排的 end;好了,经过上面几步我们的程序就完成了。这个想法虽然荒唐(....),但是不失为一个解这个题的好办法。(后面有我打的第一个线段树代码,很丑很实用!)[附AC代码]Typedatatype=record s,wz:longint; end;Vara:array[1..100000]of datatype;c:array[1..100000]of longint;i,m,n,j,k,x,y:longint;Procedure init;beginreadln(m,n);for i:=1 to m dobeginread(a[i].s);a[i].wz:=i;end;end;Procedure qsort(l,r:longint);vari,j:longint;x,y:datatype;begini:=l;j:=r;x:=a[(l+r)div 2];Repeatwhilea[i].s<x.s do inc(i);whilea[j].s>x.s do dec(j);if i<=jthen begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end;Until i>j;if i<r then qsort(i,r);if l<j then qsort(l,j);end;Begininit;qsort(1,m);k:=0;for i:=1 to n dobeginreadln(x,y);for j:=1 to m do begin if(a[j].wz>=x)and(a[j].wz<=y)thenbegininc(k);c[k]:=a[j].s;break;end; end;end;for i:=1 to k-1 do write(c[i],' ');writeln(c[k]);End.
#01:Accepted(0ms, 1804KB)
#02:Accepted(0ms, 1804KB)
#03:Accepted(0ms, 1804KB)
#04:Accepted(12ms, 1804KB)
#05:Accepted(0ms, 1804KB)
#06:Accepted(0ms, 1804KB)
#07:Accepted(0ms, 1804KB)
#08:Accepted(28ms, 1804KB)
#09:Accepted(75ms, 1804KB)
#10:Accepted(67ms, 1804KB)

Accepted/ 100 /182ms / 1804KB
[附线段树代码]Vart:array[1..100000]oflongint;//这里的树数组只开一个,记录区间最小值a:array[1..100000]oflongint;//按输入顺序记录的数组i,m,n,j,k:longint;Function min(x,y:longint):longint;beginif x<y then exit(x) elseexit(y);end;Procedure build(l,r,p:longint);//递归建立线段树varmid:longint;beginif l=r then t[p]:=a[l]elsebeginmid:=(l+r)shr 1;build(l,mid,p shl1);build(mid+1,r,(p shl1)+1);t[p]:=min(t[p shl 1],t[(pshl 1)+1]);end;end;Functiongetmin(p,l,r,gl,gr:longint):longint;//查找区间l,r的最小值Varmid,lmin,rmin:longint;Beginif (gl=l) and (gr=r) then exit(t[p]);mid:=(l+r) shr 1;if gl>mid then exit(getmin(p shl1+1,mid+1,r,gl,gr))elseif gr<=mid then exit(getmin(p shl1,l,mid,gl,gr))elsebeginlmin:=getmin(p shl 1,l,mid,gl,mid);rmin:=getmin(p shl1+1,mid+1,r,mid+1,gr);exit(min(lmin,rmin));end;//考虑三种情况:查找区间在左侧,查找区间在右侧,还有查找的区间涵盖左右侧的区域End;Beginfillchar(t,sizeof(t),0);fillchar(a,sizeof(a),0);//数组初始化,好习惯readln(m,n);for i:=1 to m do read(a[i]);build(1,m,1);for i:=1 to n dobeginreadln(j,k);write(getmin(1,1,m,j,k),'');//这里很不规范,但是tyvj评测是忽略多余空格的end;End.
TYVJP1038[忠诚] www.tyvj.cn
#01:Accepted(51ms, 2980KB)
#02:Accepted(0ms, 2980KB)
#03:Accepted(12ms, 2980KB)
#04:Accepted(4ms, 2980KB)
#05:Accepted(145ms, 2980KB)
#06:Accepted(0ms, 2980KB)
#07:Accepted(145ms, 2980KB)
#08:Accepted(75ms, 2980KB)
#09:Accepted(200ms, 2980KB)
#10:Accepted(59ms, 2980KB)

Accepted/ 100 /693ms / 2980KB

  

爱华网本文地址 » http://www.413yy.cn/a/25101011/61086.html

更多阅读

转 sptd的解释 www.sptdch.cn 8080

下载 daemontools虚拟光驱软件的时候,版本很多,但基本都是写着Daemon Tools Vx.xx (with SPTDV1.xx)这个SPTD是什么软件呢?SPTD是一个底层的硬件驱动程序,可以通过它,直接操作底层的硬件设备,比如光驱,硬盘等等,但是会程序的人都知道,这样

声明:《TYVJP1038忠诚 www.tyvj.cn》为网友狂风中拥抱你分享!如侵犯到您的合法权益请联系我们删除