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:一直超时,求大家帮我优化一下

Posted by hanhui8301 at 2017-05-22 03:15:09 on Problem 1002 and last updated at 2017-05-22 03:19:38
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:
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