{"id":944,"date":"2019-10-08T15:20:13","date_gmt":"2019-10-08T07:20:13","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=944"},"modified":"2019-10-08T15:20:13","modified_gmt":"2019-10-08T07:20:13","slug":"lp2564-scoi2009-%e7%94%9f%e6%97%a5%e7%a4%bc%e7%89%a9","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/10\/08\/lp2564-scoi2009-%e7%94%9f%e6%97%a5%e7%a4%bc%e7%89%a9\/","title":{"rendered":"lp2564 SCOI2009 \u751f\u65e5\u793c\u7269"},"content":{"rendered":"\n<p>\u5c3a\u53d6\u6cd5\u5373\u53ef\u3002<br>\n\u5f00\u4e00\u4e2a\u6876\u7ef4\u62a4\u73cd\u73e0\u7684\u989c\u8272\uff0c\u7136\u540e\u626b\u4e00\u904d\u3002\u6bcf\u4e00\u6b21\u5c06\u6700\u524d\u7aef\u7684\u70b9\u5f39\u51fa\uff0c\u7136\u540e\u79fb\u52a8\u81f3\u4e0b\u4e00\u4e2a\u5408\u6cd5\u70b9\u3002 <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cstring>\n#include&lt;algorithm>\n#include&lt;queue>\n#include&lt;vector>\nusing namespace std;\n\nconst int N=1000005;\nstruct data{\n\tint id;\n\tint val;\n}a[N];\ninline bool cmp(const data &amp;A,const data &amp;B){\n\treturn A.val&lt;B.val;\n}\nint n,K,tp=0;\nint bckt[65],cnt=0;\nvoid init(){\n\tscanf(\"%d%d\",&amp;n,&amp;K);\n\tint T;\n\tfor(int i=1;i&lt;=K;++i){\n\t\tscanf(\"%d\",&amp;T);\n\t\tfor(int j=1;j&lt;=T;++j){\n\t\t\t++tp;\n\t\t\tscanf(\"%d\",&amp;a[tp].val);\n\t\t\ta[tp].id=i;\n\t\t}\n\t}\n\tstd::sort(a+1,a+1+n,cmp);\n\tint ans=2147483647;\n\tint l=1,r=0;\n\twhile(r&lt;n){\n\t\twhile(r&lt;n){\n\t\t\t++r;\n\t\t\tif(!bckt[a[r].id]){\n\t\t\t\t++cnt;\n\t\t\t}\n\t\t\t++bckt[a[r].id];\n\t\t\tif(cnt==K){\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\tif(cnt==K){\n\t\t\tans=min(ans,a[r].val-a[l].val);\n\t\t}\n\t\twhile(l&lt;=r){\n\t\t\t--bckt[a[l].id];\n\t\t\tif(!bckt[a[l].id]){\n\t\t\t\t--cnt;\n\t\t\t\t++l;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\t++l;\n\t\t\tif(cnt==K){\n\/\/\t\t\t\tprintf(\"%d %d %d\\n\",ans,l,r);\n\t\t\t\tans=min(ans,a[r].val-a[l].val);\n\t\t\t}\n\t\t\t\n\t\t}\n\t}\n\tprintf(\"%d\\n\",ans);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u5c3a\u53d6\u6cd5\u5373\u53ef\u3002 \u5f00\u4e00\u4e2a\u6876\u7ef4\u62a4\u73cd\u73e0\u7684\u989c\u8272\uff0c\u7136\u540e\u626b\u4e00\u904d\u3002\u6bcf\u4e00\u6b21\u5c06\u6700\u524d\u7aef\u7684\u70b9\u5f39\u51fa\uff0c\u7136\u540e\u79fb\u52a8\u81f3\u4e0b\u4e00\u4e2a\u5408\u6cd5\u70b9\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[121,9,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/944"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=944"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/944\/revisions"}],"predecessor-version":[{"id":946,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/944\/revisions\/946"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=944"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}