学步园

TAG 插入排序  二分法

我是用插入排序做的，在插入的时候使用二分法查找位置。用数组idx记录下标，只移动索引，提高速度。

/* source code of submission 426993, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> const int N=100000;<br /> struct node<br /> {<br /> char name[11];<br /> int pro;<br /> };<br /> int idx[N];<br /> node stu[N];<br /> int num,t;<br /> bool flag,first;<br /> char commamd[10];<br /> int bin_search(int s, int t, int x)<br /> {<br /> int mid;<br /> int ret=t;<br /> while ( s<=t )<br /> {<br /> mid=(s+t)/2;<br /> if ( stu[ idx[mid] ].pro > x )<br /> {<br /> t=mid-1;<br /> }<br /> else<br /> {<br /> ret=mid;<br /> s=mid+1;<br /> }<br /> }<br /> return ret;<br /> }<br /> void add()<br /> {<br /> ++num;<br /> scanf("%s%d", stu[num].name, &stu[num].pro);<br /> idx[num]=num;</p> <p> if ( num>0 )<br /> {<br /> int p=bin_search(0,num-1,stu[num].pro);<br /> for (int i=num-1; i>p; --i)<br /> {<br /> idx[i+1]=idx[i];<br /> }<br /> idx[p+1]=num;<br /> }<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> scanf("%d", &t);<br /> first=true;<br /> while ( t-- )<br /> {<br /> if ( !first )<br /> {<br /> printf("/n");<br /> }<br /> else<br /> {<br /> first=false;<br /> }<br /> flag=true;<br /> num=-1;<br /> while ( flag )<br /> {<br /> scanf("%s",commamd);<br /> switch( commamd[0] )<br /> {<br /> case 'A':add();<br /> break;<br /> case 'Q': if (num%2==0)<br /> {<br /> printf("%s/n", stu[ idx[num/2] ].name);<br /> }<br /> else<br /> {<br /> printf("No one!/n");<br /> }<br /> break;<br /> case 'E': flag=false;<br /> if (num%2==0)<br /> {<br /> printf("%s is so poor./n", stu[ idx[num/2] ].name);<br /> }<br /> else<br /> {<br /> printf("Happy BG meeting!!/n");<br /> }<br /> break;<br /> }<br /> }</p> <p> }<br /> return 0;<br /> }<br />