#4480: 為何產生TLE(10S)


wwww (米豆)


/**********************************************************************************/
/*  Problem: b255 "D. 跑跑卡丁車" from 2009 NPSC 高中組決賽             */
/*  Language: CPP                                                                 */
/*  Result: TLE (10)  on ZeroJudge                                                */
/*  Author: wwww at 2010-10-30 01:01:50                                           */
/**********************************************************************************/


#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

struct world
{
      string name;           // 隊名 
      long int score;          // 排名時數 
} ; 
    
typedef struct world snd;     // 定義資料型態名稱--排名 

void sorta (snd*,int fn);              // A組排序


int main(void){  
/*    int n=1;
      cin >> n;
    while( n!=0 ){
         cin >> n;
*/      
      int n;
      while( cin >> n ){
         if ( n==0 ) { break; }
         if ( n<3 || n>100000 ) {break;}
         snd s[n];
         int hh=0,mm=0,ss=0,ms=0;
         for(int i=0;i<n;i++){
             cin >>s[i].name;
             scanf("%d:%d:%d.%d",&hh,&mm,&ss,&ms);
             s[i].score=hh*3600000+mm*60000+ss*1000+ms;
         }
             
          sorta(s,n);    //排序   
          cout<<"LIST START"<<endl;
          int k=0;
          k=n/3;
          for(int i=0;i<k;i++){
              cout <<s[i].name<<endl;
          }
          for(int i=k;i<n;i++){
              if ( s[k-1].score == s[i].score ) {
                   cout <<s[i].name<<endl;
              }     
          } 
    cout<<"LIST END"<<endl;
          
//tab_end: 
    }     
//system("pause");
return 0;

}

void sorta(snd* fs, int fn)   //A組排序 
{
     
     snd temp;
       
     for (int j=fn; j>0; j--) {
     for (int i=0; i<j-1; i++) {
          if (fs[i].score > fs[i+1].score) {
                   temp = fs[i+1];
                   fs[i+1] = fs[i];
                   fs[i] = temp;
          }
     }
     }              
}

#4481: Re:為何產生TLE(10S)


leopan0922 (zz)


/**********************************************************************************/
/*  Problem: b255 "D. 跑跑卡丁車" from 2009 NPSC 高中組決賽             */
/*  Language: CPP                                                                 */
/*  Result: TLE (10)  on ZeroJudge                                                */
/*  Author: wwww at 2010-10-30 01:01:50                                           */
/**********************************************************************************/


#include
#include
#include
using namespace std;

struct world
{
      string name;           // 隊名 
      long int score;          // 排名時數 
} ; 
    
typedef struct world snd;     // 定義資料型態名稱--排名 

void sorta (snd*,int fn);              // A組排序


int main(void){  
/*    int n=1;
      cin >> n;
    while( n!=0 ){
         cin >> n;
*/      
      int n;
      while( cin >> n ){
         if ( n==0 ) { break; }
         if ( n<3 || n>100000 ) {break;}
         snd s[n];
         int hh=0,mm=0,ss=0,ms=0;
         for(int i=0;i
             cin >>s[i].name;
             scanf("%d:%d:%d.%d",&hh,&mm,&ss,&ms);
             s[i].score=hh*3600000+mm*60000+ss*1000+ms;
         }
             
          sorta(s,n);    //排序   
          cout<<"LIST START"<
          int k=0;
          k=n/3;
          for(int i=0;i
              cout <<
          }
          for(int i=k;i
              if ( s[k-1].score == s[i].score ) {
                   cout <<
              }     
          } 
    cout<<"LIST END"<
          
//tab_end: 
    }     
//system("pause");
return 0;

}

void sorta(snd* fs, int fn)   //A組排序 
{
     
     snd temp;
       
     for (int j=fn; j>0; j--) {
     for (int i=0; i
          if (fs[i].score > fs[i+1].score) {
                   temp = fs[i+1];
                   fs[i+1] = fs[i];
                   fs[i] = temp;
          }
     }
     }              
}

n很大

O(n^2)的排序一定過不暸

請用O(nlogn)的方法

#4483: Re:為何產生TLE(10S)


asas (向諸神與地雷醬獻上祈禱)


sorta(s,n);可以改成sort(s,n,gt);其中gt自己可以定義要如何排序~~這就是O(nlogn)!!
#4486: Re:為何產生TLE(10S)


leopan0922 (zz)


sorta(s,n);可以改成sort(s,n,gt);其中gt自己可以定義要如何排序~~這就是O(nlogn)!!

不過這題要自己開struct才能用內建吧....