有趣的題目, 因為我實力不足的關係花了我幾天去想和寫和改良
這題我第一個想去就是想去binary search答案, 再看發現的確可以binary search
於是便寫了個binary search, 再找given一個n, 第k個數是多少
這個問題也不簡單, 但也不難, 花了一段時間寫完+debug, 再交得到TLE
看看discuss, 好像需要沒有binary search的做法才會不TLE, 於是再想想發現的確可以不binary search
詳細的details我想得很麻煩, 無謂寫在這裏
主要的想法就是一個一個digit去試, 直至找到most significant digit
大家花少許時間就會想到, 最後通過了之後再交PKU 2171, 竟然過不到
發現是<=和<搞亂了, 沒有詳細想清楚, 證明有些細節不想清楚的話, 雖然自己測試測不到, 但交上去還是會錯的
這題最後寫了很多個版本, 就等於做了幾道題目
不過對這類題目處理還是寫得不夠好, 想得也很慢, 希望WF之前可以改進
沒有留言:
張貼留言