{"id":38,"date":"2010-06-29T19:03:40","date_gmt":"2010-06-29T11:03:40","guid":{"rendered":"http:\/\/comzyh.gicp.net\/myblog\/?p=38"},"modified":"2010-10-01T08:11:13","modified_gmt":"2010-10-01T00:11:13","slug":"p16-%e5%90%9e%e5%99%ac%e6%af%94%e8%b5%9b-nlogn%e6%9c%80%e9%95%bf%e4%b8%8d%e4%b8%8b%e9%99%8d%e7%bb%84%e5%ba%8f%e5%88%97","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/38\/","title":{"rendered":"P156 \u541e\u566c\u6bd4\u8d5b NlogN\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217"},"content":{"rendered":"<p>MY CODE:   <\/p>\n<pre lang=\"C\">\n#include<stdio.h>\n\/\/nlogn\u7b97\u6cd5\n\/*\u628a10000\u641e\u62101000\u4e86\uff0c\u9519\u4e86\u4e00\u4e0b\u5348*\/ \nint n,max;\nint b[10001],a[10001],len[10001];\n int bins(int key) {\n    static int l,r,y;\n    l=0;r=n;\n    while (l<=r){\n          y=(l+r)>>1;\n          if (b[y]>key) r=y-1;else\n          if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}\/\/\u8fd9\u91cc\u5927\u62ec\u53f7\u4e3a\u4e86\u9605\u8bfb\u65b9\u4fbf\n          else return y;\n          }\n    }\nint main(){\n    int i,j;\n    scanf(\"%d\\n\",&n);\n    for (i=1;i<=n;i++){scanf(\"%d\",&#038;a[i]);b[i]=20000;}\n    b[0]=0;\/\/\u8fd9\u4e2a\u521d\u59cb\u5316\u8981\u6bd4\u6240\u6709\u5143\u7d20\u5c0f\n    for (i=1;i<=n;i++){\n         len[i]=bins(a[i]-1)+1;\n         if (len[i]>max) max=len[i];\n         if (b[len[i]]>a[i]) b[len[i]]=a[i];\n         }\n        printf(\"%d\",max);\n        return 0;       \n    }\n<\/pre>\n<p><!--more--><\/p>\n<h1>\u9898\u76ee\u63cf\u8ff0<\/h1>\n<p>\u9547\u91cc\u4e3e\u529e\u8d2a\u5403\u6bd4\u8d5b\uff0c\u4e00\u5171\u6bd4\u8d5bN\u5929\uff0c\u89c4\u5b9a\uff1a\u6bcf\u6b21\u5403\u7684\u5fc5\u987b\u6bd4\u4e0a\u6b21\u591a\uff0c\u4e00\u5929\u53ea\u80fd\u5403\u4e00\u6b21\uff08\u6491\u6b7b&#8230;\uff09\uff0c\u5403\u7684\u5929\u6570\u6700\u591a\u7684\u4eba\u5c06\u83b7\u5f97\u80dc\u5229\uff0c\u83b7\u5f9710000000000 mod 10 \u7684\u5956\u91d1^_^ \u73b0\u5728\uff0cSally\u8981\u53c2\u52a0\u6bd4\u8d5b\uff0c\u5979\u9080\u8bf7\u53c2\u52a0OI\u7684\u4f60\u4e00\u8d77\u5e2e\u5fd9\uff0c\u80dc\u5229\u540e\u4e03\u4e09\u5206\u6210^_^ <\/p>\n<h1>\u8f93\u5165\u683c\u5f0f<\/h1>\n<p>\u7b2c\u4e00\u884c\u4e00\u4e2a\u6570N\uff0c\u8868\u793a\u5403\u7684\u5929\u6570\uff08N&lt;=10000) \u7b2c\u4e8c\u884cN\u4e2a\u6570\uff0c\u8868\u793a\u6bcf\u5929\u80fd\u5403\u7684\u6570\u91cf\uff08\u6570\u91cf\u6700\u591a10000\uff09 <\/p>\n<h1>\u8f93\u51fa\u683c\u5f0f<\/h1>\n<p>\u4e00\u4e2a\u6570\uff0c\u8868\u793a\u6700\u591a\u5403\u7684\u5929\u6570 <\/p>\n<h1>\u6837\u4f8b\u8f93\u5165<\/h1>\n<p><textarea rows=\"rows\" cols=\"cols\" readonly=\"readonly\" name=\"textarea\">6<br \/>\n1 2 3 1 5 6<\/textarea> <\/p>\n<h1>\u6837\u4f8b\u8f93\u51fa<\/h1>\n<p><textarea rows=\"rows\" cols=\"cols\" readonly=\"readonly\" name=\"textarea2\">5 <\/textarea><\/p>\n","protected":false},"excerpt":{"rendered":"<p>MY CODE: #include \/\/nlogn\u7b97\u6cd5 \/*\u628a10000\u641e\u62101000\u4e86\uff0c\u9519\u4e86\u4e00\u4e0b\u5348*\/ int [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[4],"tags":[22,23],"class_list":["post-38","post","type-post","status-publish","format-standard","hentry","category-rqnoj","tag-nlogn","tag-23"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-C","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/38","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=38"}],"version-history":[{"count":0,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/38\/revisions"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}