{"id":19,"date":"2009-11-13T23:35:00","date_gmt":"2009-11-13T15:35:00","guid":{"rendered":"http:\/\/localhost\/?p=19"},"modified":"2009-11-13T23:35:00","modified_gmt":"2009-11-13T15:35:00","slug":"spoj_297","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=19","title":{"rendered":"SPOJ 297"},"content":{"rendered":"<p> \u3002\u3002\u3002\u4f20\u9001\u95e8\u3002\u3002\u3002<br \/>http:\/\/www.spoj.pl\/problems\/AGGRCOW\/\u3002\u3002\u3002<br \/>\u4e8c\u5206+\u8d2a\u5fc3\u9ebb\u3002\u3002\u5f88\u660e\u663e\u5982\u679c\u77e5\u9053\u7b54\u6848\u8d8a\u5f80\u94b1\u653e\u8d8a\u597d\u561b\u3002\u3002\u3002<br \/>\u4ee3\u7801\u592a\u77ed\u4e86\u3002\u3002\u3002<br \/>#include&lt;iostream&gt;<br \/>#include&lt;cstdio&gt;<br \/>#include&lt;algorithm&gt;<br \/>using namespace std;<br \/>const int maxn=100000;int N,C,X[maxn];<br \/>bool Can(int limit)<br \/>{<br \/>int old=0,now=1;<br \/>for(int i=1;i&lt;C;i++)<br \/>{<br \/>while(X[now]-X[old]&lt;limit&amp;&amp;now&lt;N)<br \/>now++;<br \/>if(now&gt;=N)<br \/>return false;<br \/>old=now;now++;<br \/>}<br \/>return true;<br \/>}<br \/>void solve();<br \/>int main()<br \/>{<br \/>int t;cin&gt;&gt;t;<br \/>while(t&#8211;)<br \/>{&#160;&#160;&#160; &#160;&#160;&#160; <br \/>solve();<br \/>}<br \/>}<br \/>void solve()<br \/>{<br \/>cin&gt;&gt;N&gt;&gt;C;<br \/>for(int i=0;i&lt;N;i++)<br \/>scanf(&quot;%d&quot;,X+i);<br \/>sort(X,X+N);<br \/>int l=1,r=X[N-1];<br \/>while(l+1&lt;r)<br \/>{<br \/>int mid=(l+r)\/2;<br \/>if(Can(mid))<br \/>l=mid;<br \/>else<br \/>r=mid;<br \/>}<br \/>cout&lt;&lt;l&lt;&lt;endl;<br \/>} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u3002\u3002\u3002\u4f20\u9001\u95e8\u3002\u3002\u3002http:\/\/www.spoj.pl\/problems\/AGGRCOW\/\u3002\u3002\u3002\u4e8c\u5206+\u8d2a\u5fc3\u9ebb\u3002\u3002\u5f88\u660e\u663e\u5982\u679c\u77e5\u9053\u7b54\u6848\u8d8a\u5f80\u94b1\u653e\u8d8a\u597d\u561b\u3002\u3002\u3002\u4ee3\u7801\u592a\u77ed\u4e86\u3002\u3002\u3002#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;algorithm&gt;using namespace std;const int maxn=100000;int N,C,X[maxn];bool Can(int limit){int old=0,now=1;for(int i=1;i&lt;C;i++){while(X[now]-X[old]&lt;limit&amp;&amp;now&lt;N)now++;if(now&gt;=N)return false;old=now;now++;}return true;}void solve();int main(){int t;cin&gt;&gt;t;while(t&#8211;){&#160;&#160;&#160; &#160;&#160;&#160; solve();}}void solve(){cin&gt;&gt;N&gt;&gt;C;for(int i=0;i&lt;N;i++)scanf(&quot;%d&quot;,X+i);sort(X,X+N);int l=1,r=X[N-1];while(l+1&lt;r){int mid=(l+r)\/2;if(Can(mid))l=mid;elser=mid;}cout&lt;&lt;l&lt;&lt;endl;}<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/19"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=19"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/19\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}