Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:一个O(N)复杂度的解法,欢迎评论

Posted by Zdoujiang at 2016-04-01 09:21:35 on Problem 1007
In Reply To:一个O(N)复杂度的解法,欢迎评论 Posted by:njuallen at 2015-02-08 23:39:52
> #include<stdio.h>           //这是一个O(N)的解法,以前的那个优质解法的帖子中的算法是O(N^2)的,实际跑出来,我的解法16MS,那个解法32MS,说明这个优化还算可以的。        
> #include<stdlib.h>                     
> 
> int cmp(const void * a, const void * b)  
> {
> 	return((*(int*)a-*(int*)b));
> }
> 
> int measure(char *str,int len)
> {
> 	int tmp_C=0,tmp_G=0,tmp_T=0;          
> int front_C=0,front_G=0,front_T=0;
> int total_C=0,total_G=0,total_T=0;
> 	int exist_C=0,exist_G=0,exist_T=0;
> 	for(int i=len-1;i>=0;i--)
> 	{
> 		switch (str[i])
> 		{
> 			case 'A':
> 				tmp_C++;
> 				tmp_G++;
> 				tmp_T++;
> 				break;
> 			case 'C':
> 				exist_C=1;
> 				tmp_G++;
> 				tmp_T++;
> 				front_C+=tmp_C;
> 				total_C+=front_C;
> 				tmp_C=0;
> 				break;
> 			case 'G':
> 				exist_G=1;
> 				tmp_T++;
> 				front_G+=tmp_G;
> 				total_G+=front_G;
> 				tmp_G=0;
> 				break;
> 			case 'T':
> 				exist_T=1;
> 				front_T+=tmp_T;
> 				total_T+=front_T;
> 				tmp_T=0;
> 				break;
> 			default:
> 				printf("Error:illegal character!");
> 		}
> 	}
> 	return exist_C*total_C+exist_G*total_G+exist_T*total_T;
> }
> 
> int main()
> {
> 	int str_len,str_num;
> 	scanf("%d %d",&str_len,&str_num);
> 	char (*p)[str_len+1]=(char(*)[str_len+1])malloc(sizeof(char)*(str_len+1)*str_num);
> 	int *result=(int *)malloc(sizeof(int)*str_num);
> 	for(int i=0;i<str_num;i++)
> 	{
> 		scanf("%s",p[i]);
> 		result[i]=measure(p[i],str_len)*1000+i;        //秩与下标的绑定
> 	};
> 	qsort(result,str_num,sizeof(int),cmp);
> 	for(int i=0;i<str_num;i++)
> 		printf("%s\n",p[result[i]%1000]);
> 	free(p);
> 	free(result);
> 	return 0;
> }
> /*此代码中秩绑定的使用以及函数指针的使用,都是借鉴的以前某位大神的优质算法那个帖子中的,它们让代码更简洁,更漂亮,在此谢谢那位大神。我的代码中,大量使用了case语句,我感觉很丑陋,想到解决办法的请协助改进,谢谢。*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator