| ||||||||||
| 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