第一题Range
关键：二分查找，查找不大于一个数的最大下标。
1 #include <cstdlib> 2 #include <cstdio>
4 int compare (const void * a, const void * b){ 5 return ( *(int*)a - *(int*)b ); 6 } 7 int bisearch(int *array,int low, int high,int aim){ 8 int mid; 9 while(low<=high){ 10 mid = (low+high)>>1; 11 if(aim<array[mid]) 12 high=mid-1; 13 else if(aim>array[mid]) 14 low=mid+1; 15 else 16 return mid; 17 } 18 // printf("%d ",high); 19 return high; 20 } 21 int main(int argc, char* argv[]){ 22 // freopen("in.txt", "r", stdin); 23 int pnum,qtime; 24 scanf("%d %d",&pnum,&qtime); 25 int *points = new int[pnum]; 26 for(int i=0; i<pnum; i++) 27 scanf("%d",&points[i]); 28 qsort(points,pnum,sizeof(int),compare); 29 int lower,higher;//range 30 int left,right; 31 for(int i=0; i<qtime; i++){ 32 scanf("%d %d",&lower,&higher); 33 left=bisearch(points,0,pnum-1,lower); 34 right=bisearch(points,0,pnum-1,higher); 35 if(right<0){//notice 36 printf("0 "); 37 continue; 38 } 39 if(left<0){//notice 40 printf("%d ",right+1); 41 continue; 42 } 43 if(points[left]==lower){ 44 printf("%d ",right-left+1); 45 }else 46 printf("%d ",right-left); 47 } 48 delete [] points; 49 return 0; 50 }
当使用cin/cout时候，Exceed Time Limit；此外，我还比较了使用静态分配数组和动态堆分配数组的运行时间差异，发现几乎相同。
第二题祖玛，自己尝试写了一个简单的双向链表，能进行插入和删除。20个案例，最后一个超时。此外，这个题也是C/C++混杂起来使用，好尴尬。
1 #include <cstdio> 2 #include <string> 3 #include <iostream> 4 using namespace std; 5 class Node{ 6 public: 7 Node* prev; 8 Node* next; 9 char content; 10 Node():prev(NULL),next(NULL),content(0){} 11 Node(char c):prev(NULL),next(NULL),content(c){} 12 }; 13 class Dolist{ 14 public: 15 Node head; 16 int len; 17 Dolist(string in); 18 ~Dolist(); 19 Node* insert(int pos, char ch); 20 void del(Node *inpos); 21 void print(); 22 }; 23 Dolist::~Dolist(){ 24 Node *fir=head.next; 25 while(fir){ 26 Node *next=fir->next; 27 delete fir; 28 fir=next; 29 } 30 } 31 Node* Dolist::insert(int pos, char ch){ 32 Node *tmp = new Node(ch); 33 Node* cur=&head; 34 //pos<=len 35 if(pos==len){//insert in the end 36 while(cur->next){ 37 cur=cur->next; 38 } 39 cur->next=tmp; 40 tmp->prev=cur; 41 }else{ 42 for(int i=0;i<pos;i++){ 43 cur=cur->next; 44 } 45 Node* nex=cur->next; 46 cur->next=tmp; 47 tmp->prev=cur; 48 tmp->next=nex; 49 nex->prev=tmp; 50 } 51 len++; 52 return tmp; 53 } 54 void Dolist::del(Node *inpos){ 55 if(inpos==&head) 56 return; 57 int dellen=1;//num of same nodes 58 Node *fir=inpos,*las=inpos;//pointers between same nodes,from beginning to end 59 while(fir->content==fir->prev->content){//search left 60 dellen++; 61 fir=fir->prev; 62 } 63 while(las->next){//search right 64 if(las->content==las->next->content){ 65 dellen++; 66 las=las->next; 67 }else 68 break; 69 } 70 if(dellen>=3){//if num is above to 3,delete 71 Node *tmp=fir->prev; 72 fir->prev->next=las->next; 73 if(las->next) 74 las->next->prev=fir->prev; 75 Node *tmp1=fir->next; 76 while(tmp1!=las){ 77 delete fir; 78 fir=tmp1; 79 tmp1=fir->next; 80 } 81 delete fir; 82 delete las; 83 len -= dellen; 84 del(tmp);//iteration 85 86 } 87 } 88 void Dolist::print(){ 89 if(head.next==NULL) 90 printf("- "); 91 else{ 92 Node *tmp=head.next; 93 while(tmp){ 94 putchar(tmp->content); 95 tmp=tmp->next; 96 } 97 printf(" "); 98 } 99 } 100 Dolist::Dolist(string in){ 101 len=0; 102 int siz=in.size(); 103 for(int i=0; i<siz; i++){ 104 insert(i,in[i]); 105 } 106 } 107 int main(int argc, char* argv[]){ 108 //freopen("in.txt","r",stdin); 109 string init; 110 getline(cin,init); 111 Dolist zuma(init);//initial 112 int time; 113 scanf("%d",&time); 114 int pos; 115 char ch; 116 while(time--){ 117 scanf("%d %c",&pos,&ch); 118 Node *inpos = zuma.insert(pos,ch); 119 zuma.del(inpos); 120 zuma.print(); 121 } 122 return 0; 123 }
第三题灯塔，先对x坐标使用快速排序，排序后对y坐标进行归并排序，在归并排序的同时求出顺序对的数目。20个案例通过19个，最后一个超时。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 using namespace std; 5 typedef struct tower{ 6 int x; 7 int y; 8 }Tower; 9 int compare(const void *a,const void *b){ 10 return ((*(Tower*)a).x - (*(Tower*)b).x); 11 } 12 long long Merge(int *array, int m, int mid, int n){ 13 long long tmp=0; 14 int *copy=new int[n-m+1]; 15 int i,j,k=0; 16 for(i=m,j=mid+1;i<=mid&&j<=n;){ 17 if(array[i]<array[j]){ 18 copy[k]=array[i]; 19 tmp += (n-j+1);//这是最关键的，在进行merge时，如果array[i]<array[j]，那么从j到n的数都大于array[i] 20 i++; 21 }else{ 22 copy[k]=array[j]; 23 j++; 24 } 25 k++; 26 } 27 if(i<=mid){ 28 for(int ii=i; ii<=mid; ii++){ 29 copy[k]=array[ii]; 30 k++; 31 } 32 }else if(j<=n){ 33 for(int ii=j; ii<=n; ii++){ 34 copy[k]=array[ii]; 35 k++; 36 } 37 } 38 memcpy(array+m,copy,(n-m+1)*sizeof(int)); 39 delete [] copy; 40 return tmp; 41 } 42 long long MergeSort(int *array, int m, int n){ 43 if(m==n) return 0; 44 int mid = m+((n-m)>>1); 45 long long num1 = MergeSort(array,m,mid); 46 long long num2 = MergeSort(array,mid+1,n); 47 long long num3 = Merge(array,m,mid,n); 48 return num1+num2+num3; 49 } 50 51 int main(int argc,char *argv[]){ 52 //freopen("in.txt","r",stdin); 53 int num; 54 scanf("%d",&num); 55 Tower *all = new Tower[num]; 56 for(int i=0; i<num; i++){ 57 scanf("%d %d",&(all[i].x),&(all[i].y)); 58 } 59 qsort(all,num,sizeof(Tower),compare); 60 int *ally = new int[num];//取出所有的y,通过归并排序求出顺序对 61 for(int i=0; i<num; i++) 62 ally[i]=all[i].y; 63 long long out = MergeSort(ally,0,num-1); 64 printf("%lld ",out); 65 delete [] all; 66 delete [] ally; 67 return 0; 68 }