作者yoco315 (眠月)
看板C_and_CPP
標題Re: [問題] 找兩個已排序陣列共同的數
時間Sat Dec 12 02:17:16 2009
有沒有大大可以幫我看一下，我可以接受他說我太慢，但是 wa 是怎樣 ~_~"
我照足上一篇的虛擬碼 code 的阿 Orz
┌────────────────────────────────────┐
｜int main () { │
｜ // 宣告 │
｜ size_t n = 0 ; │
｜ size_t m = 0 ; │
｜ std::cin >> n >> m ; │
｜ size_t *a = new size_t[m] ; │
｜ size_t *b = new size_t[m] ; │
｜ for ( size_t i=0; i<n; ++i ) { │
｜ // 讀取 │
｜ for ( size_t j=0; j<m; ++j ) { std::cin >> a[j] ; } │
｜ for ( size_t j=0; j<m; ++j ) { std::cin >> b[j] ; } │
｜ size_t x = 0 ; │
｜ size_t y = 0 ; │
｜ size_t same_cnt = 0 ; │
｜ // 演算法主要部份 │
｜ for (;;) { │
｜ if ( x == m || y == m ) { │
｜ break ; │
｜ } │
｜ if ( a[x] == b[y] ) { │
｜ ++same_cnt ; │
｜ ++x ; │
｜ ++y ; │
｜ } │
｜ else if ( a[x] < b[y] ) { │
｜ ++x ; │
｜ } │
｜ else { │
｜ ++y ; │
｜ } │
｜ } │
｜ std::cout << same_cnt << std::endl ; │
｜ } │
｜ delete[] a ; │
｜ delete[] b ; │
｜ return 0 ; │
｜} │
└────────────────────────────────────┘
T______T 我太無能了，對不起
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.113.127
1F：→ cismjmgoshr:問個問題... size_t的範圍是0~2^64-1嗎 @@? 12/12 02:25
2F：→ yoco315:這個.. 看環境 orz 12/12 02:31
3F：→ yoco315:挖勒AC了，size_t的問題，改成 unsigne long long 就好了 12/12 02:41
4F：→ akasan:90ms收工XD 12/12 02:48
5F：→ yoco315:是直接 ioctl 嗎.. 這題瓶頸根本就在 input XD 12/12 02:50
6F：→ yoco315:algo 就算 bs O(logn)，input 還是 O(n) XD 12/12 02:51
7F：→ akasan:其實我們用的是同一個演算法XD 頻頸是在轉換 str->num 12/12 02:53
8F：→ yoco315:我實際上是getchar()自己轉了.. 12/12 02:54
9F：→ yoco315:貼出來的 code 是想說正規一點.. 12/12 02:55
10F：→ akasan:不用轉最快! 12/12 02:56
11F：→ yoco315:這就是為什麼你記憶體用這麼多嗎. 12/12 02:57
12F：→ yoco315:剛剛就注意到你記憶體用很多,我還想不透,原來如此 XD 12/12 02:58