http://www.spoj.pl/problems/COWCAR/
实际上我最近做的SPOJ的题目都是一些ＵＳＡＣＯ月赛的老题。。。
感觉ＵＳＡＣＯ月赛的题目跟我们ＯＩ是比较贴近的。。
不过中国就是没有美国开放。。连stl都不能用。。
说实话我连heap也不会写。。要是ＮＯＩＰ要用我只好写左偏树了。。
这道题实际上很水。。把所有牛按速度排序。。再一个个处理。。
很明显要把每个牛放到当前能承受值最小的轨道。。放不了就扔掉。。。
Code。。
我为了图方便把所有数取负了。。。
#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;
}