V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
yongzhong
V2EX  ›  Python

python 刷题时遇到的坑

  •  
  •   yongzhong · 2015-10-20 16:02:13 +08:00 · 3508 次点击
    这是一个创建于 3306 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在用 python 刷 cf 水题的时候经常会遇到一些莫名其妙的问题,今天又遇到了一个
    在这么个题的时候 http://codeforces.com/contest/274/problem/A 得到 Time limit exceeded on test 9
    查看详情发现这组测试数据都比较大,而我的代码明明就和其他人的 ac 代码一样(java,c++.翻了好几页也没有找到 python 的 ac 甚至提交)

    是我的代码不对还是真的踩到坑了?
    以下是我的代码,py3

    # coding=utf-8
    n, k = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    a.sort()
    s = []
    for i in a:
        if i % k != 0 or i / k not in s:
            s.append(i)
    print(len(s))
    
    10 条回复    2015-10-20 22:23:36 +08:00
    lrqrun
        1
    lrqrun  
       2015-10-20 16:19:55 +08:00
    Time limit exceeded ,测试数据这么大还是换语言吧, python 计算这么慢肯定超时的。
    yongzhong
        2
    yongzhong  
    OP
       2015-10-20 16:29:01 +08:00
    @lrqrun 主要想着 python 写起来方便.c/c++不熟,java 那代码量又....
    mickeyandkaka
        3
    mickeyandkaka  
       2015-10-20 16:33:40 +08:00
    cf faq 说过不保证所有语言在用正确算法的情况下能在给定时间内通过,所以还是换 c/c++吧。
    paw
        4
    paw  
       2015-10-20 16:41:19 +08:00
    用 pypy 试试
    billgreen1
        5
    billgreen1  
       2015-10-20 16:44:51 +08:00
    list 的 in 操作 和 append 都是比较耗时的,试试 dict ?
    还有,既然都是 sorted ,当 i * k > max(a)的时候,还有必要继续下去吗?
    cysu
        6
    cysu  
       2015-10-20 16:47:24 +08:00   ❤️ 1
    有用 py3 过的 http://codeforces.com/contest/274/submission/11605253
    善用右边搜索功能 XD...
    lll9p
        7
    lll9p  
       2015-10-20 16:49:09 +08:00
    用 set 会快非常多
    starsoi
        8
    starsoi  
       2015-10-20 16:49:10 +08:00
    py3 的坑
    i / k not in s: i / k 的结果是 float...
    应该用 //
    yongzhong
        9
    yongzhong  
    OP
       2015-10-20 17:03:42 +08:00
    @cysu
    @starsoi
    in s 这个操作花费了大量时间,代码没到位
    niseceric
        10
    niseceric  
       2015-10-20 22:23:36 +08:00
    @yongzhong 直接用 set() 为什么要排序? list 的 member test 是 O(n), set/dict 是 O(1)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1100 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 19:06 · PVG 03:06 · LAX 11:06 · JFK 14:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.