1.題目描述
http://poj.org/problem?id=1002
2.解題過程
按部就班來解題的話，這個題目很容易寫出來，這是我的第一個版本的代碼，思路是讀入一行電話字符串，均轉化為整型數字存入vector結構，然後進行排序，順序統計即可發現重復的電話號碼及次數。
<iostream>
<vector>
<iterator>
<string>
<algorithm>
std;
cvtString2Int(string & str);
normalizedOutput( tel, &count);
showDump(vector<> & telNum);
sortAsc( & v1 , & v2)
{
v1<v2;
}
main()
{
count;
vector<> input_tel;
cin>>count;
string curTel;
curTelInt;
( i=0;i<count;++i)
{
cin>> curTel;
input_tel.push_back(cvtString2Int(curTel));
}
showDump(input_tel);
1;
}
cvtString2Int(string & str)
{
ret = 0;
( i = 0; i< str.length(); ++i)
{
(str[i] == ) ;
digit;
(str[i]>=&&str[i]<=)
{
digit = str[i] - ;
}
{
(str[i] < &&str[i]>)
{
digit = (str[i] - )/3 + 7;
}
(str[i]>= &&str[i]<)
{
digit = (str[i] - )/3 + 2;
}
}
ret = 10 * ret + digit;
}
ret;
}
normalizedOutput( tel, &count)
{
cout<<endl;
vector<> result;
bitNum = 0;
(tel!=0)
{
result.push_back(tel%10);
tel /=10;
bitNum ++;
}
hy = 0;
(bitNum<7)
{
cout << ;
hy++;
(hy == 3)cout << ;
bitNum ++;
}
vector<>::reverse_iterator iter;
(iter = result.rbegin();iter!= result.rend();++iter)
{
cout<<*iter;
hy++;
(hy == 3)cout<<;
}
cout<<<<count;
}
showDump(vector<> & telNum)
{
flag = 0;
count = 1;
vector<>::iterator iter;
curTel = -1;
(iter = telNum.begin(); iter != telNum.end(); ++iter)
{
(curTel == *iter){count ++;}
{
(count>1)
{
normalizedOutput(curTel ,count);
count = 1;
curTel = *iter;
(flag == 0 ) flag = 1;
}
{
curTel = *iter;
}
}
}
(count >1)
{
normalizedOutput(curTel,count);
(flag == 0 )flag = 1;
}
(flag == 0)
{
cout<<;
}
}
在數據量較小時,這種解法沒有問題,但是一旦輸入數據變多,程序的效率就會出現大問題,比如這個用這個代碼在提交online judge的時候就出現了””錯誤，最開始以為，程序運行效率的瓶頸在於這句話，眾所周知，目前排序算法的效率最好也只有O(NlgN)，本題最大輸入數目為100000，在極端情況下效率是不行的。
sort(input_tel.begin(),input_tel.end(),sortAsc);
但是，本著實事求是的態度，我在機器上測了一下這句話的運行時間，測試方法如下（在main函數中加入時間戳）：
main()
{
count;
vector<> input_tel;
cin>>count;
string curTel;
curTelInt;
( i=0;i<count;++i)
{
cin>> curTel;
input_tel.push_back(cvtString2Int(curTel));
}
clock_t start, finish;
start = clock();
sort(input_tel.begin(),input_tel.end(),sortAsc);
finish = clock();
cout<< <<start<<<<finish<<<<()(finish-start)<<<<()(finish-start)/CLOCKS_PER_SEC <<endl;
showDump(input_tel);
finish = clock();
cout<< <<start<<<<finish<<<<()(finish-start)<<<<()(finish-start)/CLOCKS_PER_SEC <<endl;
1;
}
得到的結果大大出乎我的意料，我用73728個數據進行極端測試，結果發現，排序所用時間其實很短，下面是運行結果
![]()
仔細分析覺得可能是online judge把我的輸入時間算在總時間裡面了，這樣的話cin的效率必須考慮，網上搜了一下，發現C++和G++在cin的效率上差別還蠻大的，於是編譯器改成了C++，這樣一來竟然直接就AC了，汗~（因為程序我是在minGW中調試的，所以submit的時候我一直選G++）。
一般提交時，對於c++程序，用G++或者C++，根據poj中FAQ的描述：
![]()
std::ios::sync_with_stdio(false);
具體原因在 中有解釋，大概意思就是“對於G++,默認的時候，cin與stdin總是保持同步的，也就是說這兩種方法可以混用，而不必擔心文件指針混亂，同時cout和stdout也一樣，兩者混用不會輸出順序錯亂。正因為這個兼容性的特性，導致cin有許多額外的開銷，如何禁用這個特性呢？只需剛才的語句即可”。總之，不敏感，前後效率相同。反過來MINGW則非常敏感，前後效率相差8倍。
一般來講，linux程序會比window上的程序效率高一點，在用G++和C++都能AC過之後，
![]()
normalizedOutput( & tel, &count)
{
cout<<tel/1000000<<tel/100000%10<<tel/10000%10<<;
cout<<tel/1000%10<<tel/100%10<<tel/10%10<<tel%10<<<<count<<endl;
}
//或者直接寫入showDump函數中，畢竟調用函數也有開銷。
這麼一改進之後，程序效率進一步提高，
![]()
<iostream>
<vector>
<iterator>
<string>
<algorithm>
std;
cvtString2Int(string & str);
normalizedOutput( &tel, &count);
showDump(vector<> & telNum);
sortAsc( & v1 , & v2)
{
v1<v2;
}
main()
{
count;
vector<> input_tel;
std::ios::sync_with_stdio(false);
cin>>count;
string curTel;
curTelInt;
( i=0;i<count;++i)
{
cin>> curTel;
input_tel.push_back(cvtString2Int(curTel));
}
sort(input_tel.begin(),input_tel.end(),sortAsc);
showDump(input_tel);
1;
}
cvtString2Int(string & str)
{
ret = 0;
( i = 0; i< str.length(); ++i)
{
(str[i] == ) ;
digit;
(str[i]>=&&str[i]<=)
{
digit = str[i] - ;
}
{
(str[i] < &&str[i]>)
{
digit = (str[i] - )/3 + 7;
}
(str[i]>= &&str[i]<)
{
digit = (str[i] - )/3 + 2;
}
}
ret = 10 * ret + digit;
}
ret;
}
normalizedOutput( & tel, &count)
{
cout<<tel/1000000<<tel/100000%10<<tel/10000%10<<;
cout<<tel/1000%10<<tel/100%10<<tel/10%10<<tel%10<<<<count<<endl;
}
showDump(vector<> & telNum)
{
flag = 0;
count = 1;
vector<>::iterator iter;
curTel = -1;
(iter = telNum.begin(); iter != telNum.end(); ++iter)
{
(curTel == *iter){count ++;}
{
(count>1)
{
normalizedOutput(curTel ,count);
count = 1;
curTel = *iter;
(flag == 0 ) flag = 1;
}
{
curTel = *iter;
}
}
}
(count >1)
{
normalizedOutput(curTel,count);
(flag == 0 )flag = 1;
}
(flag == 0)
{
cout<<;
}
}
