{"id":30,"date":"2009-11-15T10:51:00","date_gmt":"2009-11-15T02:51:00","guid":{"rendered":"http:\/\/localhost\/?p=30"},"modified":"2009-11-15T10:51:00","modified_gmt":"2009-11-15T02:51:00","slug":"spoj_2714","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=30","title":{"rendered":"SPOJ 2714"},"content":{"rendered":"

http:\/\/www.spoj.pl\/problems\/COWCAR\/
\u5b9e\u9645\u4e0a\u6211\u6700\u8fd1\u505a\u7684SPOJ\u7684\u9898\u76ee\u90fd\u662f\u4e00\u4e9b\uff35\uff33\uff21\uff23\uff2f\u6708\u8d5b\u7684\u8001\u9898\u3002\u3002\u3002
\u611f\u89c9\uff35\uff33\uff21\uff23\uff2f\u6708\u8d5b\u7684\u9898\u76ee\u8ddf\u6211\u4eec\uff2f\uff29\u662f\u6bd4\u8f83\u8d34\u8fd1\u7684\u3002\u3002
\u4e0d\u8fc7\u4e2d\u56fd\u5c31\u662f\u6ca1\u6709\u7f8e\u56fd\u5f00\u653e\u3002\u3002\u8fdestl\u90fd\u4e0d\u80fd\u7528\u3002\u3002
\u8bf4\u5b9e\u8bdd\u6211\u8fdeheap\u4e5f\u4e0d\u4f1a\u5199\u3002\u3002\u8981\u662f\uff2e\uff2f\uff29\uff30\u8981\u7528\u6211\u53ea\u597d\u5199\u5de6\u504f\u6811\u4e86\u3002\u3002
\u8fd9\u9053\u9898\u5b9e\u9645\u4e0a\u5f88\u6c34\u3002\u3002\u628a\u6240\u6709\u725b\u6309\u901f\u5ea6\u6392\u5e8f\u3002\u3002\u518d\u4e00\u4e2a\u4e2a\u5904\u7406\u3002\u3002
\u5f88\u660e\u663e\u8981\u628a\u6bcf\u4e2a\u725b\u653e\u5230\u5f53\u524d\u80fd\u627f\u53d7\u503c\u6700\u5c0f\u7684\u8f68\u9053\u3002\u3002\u653e\u4e0d\u4e86\u5c31\u6254\u6389\u3002\u3002\u3002
Code\u3002\u3002
\u6211\u4e3a\u4e86\u56fe\u65b9\u4fbf\u628a\u6240\u6709\u6570\u53d6\u8d1f\u4e86\u3002\u3002\u3002
#include<queue>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<functional>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxm=50000;
int N,M,D,L;
int S[maxm];
void init()
{
cin>>N>>M>>D>>L;
REP(i,N) scanf("%d",S+i);
sort(S,S+N);
}
int main()
{
init();
priority_queue<int> Q;
REP(i,M) Q.push(-L);
int ans=0;
for(int i=0;i<N;i++)
{
int cur=-Q.top();
if(cur>S[i])
continue;
Q.pop();cur+=D;Q.push(-cur);ans++;
}
cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

http:\/\/www.spoj.pl\/problems\/COWCAR\/\u5b9e\u9645\u4e0a\u6211\u6700\u8fd1\u505a\u7684SPOJ\u7684\u9898\u76ee\u90fd\u662f\u4e00\u4e9b\uff35\uff33\uff21\uff23\uff2f\u6708\u8d5b\u7684\u8001\u9898\u3002\u3002\u3002\u611f\u89c9\uff35\uff33\uff21\uff23\uff2f\u6708\u8d5b\u7684\u9898\u76ee\u8ddf\u6211\u4eec\uff2f\uff29\u662f\u6bd4\u8f83\u8d34\u8fd1\u7684\u3002\u3002\u4e0d\u8fc7\u4e2d\u56fd\u5c31\u662f\u6ca1\u6709\u7f8e\u56fd\u5f00\u653e\u3002\u3002\u8fdestl\u90fd\u4e0d\u80fd\u7528\u3002\u3002\u8bf4\u5b9e\u8bdd\u6211\u8fdeheap\u4e5f\u4e0d\u4f1a\u5199\u3002\u3002\u8981\u662f\uff2e\uff2f\uff29\uff30\u8981\u7528\u6211\u53ea\u597d\u5199\u5de6\u504f\u6811\u4e86\u3002\u3002\u8fd9\u9053\u9898\u5b9e\u9645\u4e0a\u5f88\u6c34\u3002\u3002\u628a\u6240\u6709\u725b\u6309\u901f\u5ea6\u6392\u5e8f\u3002\u3002\u518d\u4e00\u4e2a\u4e2a\u5904\u7406\u3002\u3002\u5f88\u660e\u663e\u8981\u628a\u6bcf\u4e2a\u725b\u653e\u5230\u5f53\u524d\u80fd\u627f\u53d7\u503c\u6700\u5c0f\u7684\u8f68\u9053\u3002\u3002\u653e\u4e0d\u4e86\u5c31\u6254\u6389\u3002\u3002\u3002Code\u3002\u3002\u6211\u4e3a\u4e86\u56fe\u65b9\u4fbf\u628a\u6240\u6709\u6570\u53d6\u8d1f\u4e86\u3002\u3002\u3002#include<queue>#include<cstdio>#include<algorithm>#include<iostream>#include<functional>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;const int maxm=50000;int N,M,D,L;int S[maxm];void init(){ cin>>N>>M>>D>>L; REP(i,N) scanf("%d",S+i); sort(S,S+N);}int main(){ init(); priority_queue<int> Q; REP(i,M) Q.push(-L); int ans=0; for(int i=0;i<N;i++) { int cur=-Q.top(); if(cur>S[i]) continue; Q.pop();cur+=D;Q.push(-cur);ans++; } cout<<ans<<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\/30"}],"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=30"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/30\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=30"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=30"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=30"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}