Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:一直超时,求大家帮我优化一下In Reply To:一直超时,求大家帮我优化一下 Posted by:ZhengChang at 2017-05-10 21:18:20 应该就是排序算法复杂度太高,建议用hash 或平衡 二叉树 > #include <iostream> > #include<stdio.h> > #include<string> > #include<algorithm> > using namespace std; > struct dial > { > string str; > int frequency; > int index; > bool operator < (const dial temp)const > { > return str<=temp.str; > } > } dia[100000]; > char dial_trans(char x) > { > if(x=='A'||x=='B'||x=='C') > return '2'; > else if(x=='D'||x=='E'||x=='F') > return '3'; > else if(x=='G'||x=='H'||x=='I') > return '4'; > else if(x=='J'||x=='K'||x=='L') > return '5'; > else if(x=='M'||x=='N'||x=='O') > return '6'; > else if(x=='P'||x=='R'||x=='S') > return '7'; > else if(x=='T'||x=='U'||x=='V') > return '8'; > else if(x=='W'||x=='X'||x=='Y') > return '9'; > } > int main() > { > int n,L; > while(cin>>n) > { > for(int i=0; i<n; i++) > { > cin>>dia[i].str; > for(int j=0; j<dia[i].str.size(); j++) > { > if(dia[i].str[j]=='-') > { > dia[i].str.erase(j,1); > } > } > for(int j=0; j<dia[i].str.size(); j++) > { > if(dia[i].str[j]<='Z'&&dia[i].str[j]>='A') > dia[i].str[j]=dial_trans(dia[i].str[j]); > } > dia[i].frequency=1; > dia[i].index=1; > } > for(int i=0; i<n; i++) > { > if(dia[i].index==0) > continue; > dia[i].index=0; > for(int j=0; j<n; j++) > { > if(dia[j].index==0) > continue; > if(j!=i&&dia[i].str==dia[j].str) > { > dia[i].frequency++; > dia[j].index=0; > } > } > } > int count_temp=0; > for(int i=0; i<n; i++) > { > if(dia[i].frequency>1) > { > dia[i].str.insert(3,"-"); > dia[count_temp]=dia[i]; > count_temp++; > } > } > if(count_temp==0) > printf("No duplicates.\n"); > else > { > sort(dia,dia+count_temp); > for(int i=0; i<count_temp; i++) > { > cout<<dia[i].str<<" "<<dia[i].frequency<<endl; > } > } > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator