描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1623
n头牛,第i头牛的速度是si,m条路(m<=n).如果第i头牛前面有k头牛,它的速度变为si-k*d,速度不能小于l.问最多多少头牛在路上跑.
分析
贪心啊贪心,可惜智障的我不会...
1.首先来考虑怎么分配道路.由于影响后排牛的速度的因素只有前排牛的数量,比起在一条路上排长队,把牛们尽可能均匀地分配到每一条道路上的做法会让前排的牛更少,这样后面的牛需要减的速度就更小,就有可能有更多牛在路上跑.
2.再来考虑怎么分配牛.比起把速度大的牛放在前排,把速度小的牛放在前排的做法可能会让更多的牛在路上跑,因为速度大的牛更优秀,所以更优可能能在前排牛很多的情况下依然跑.
所以算法就是先把牛们的速度排个序,然后一层一层地放牛...
p.s.普及组都没有人要系列...
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,m,d,l,ans;
int s[maxn];
int main(){
scanf("%d%d%d%d",&n,&m,&d,&l);
for(int i=;i<=n;i++) scanf("%d",&s[i]);
sort(s+,s+n+);
for(int i=;i<=n;i++)if(s[i]-ans/m*d>=l) ans++;
printf("%d\n",ans);
return ;
}
1623: [Usaco2008 Open]Cow Cars 奶牛飞车
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 416 Solved: 290
[Submit][Status][Discuss]
Description
生.每条车道上,如果某一只奶牛i的前面有K只奶牛驾车行驶,那奶牛i的速度上限就会下降K*D个单位,也就是说,她的速度不会超过
Si - kD(O≤D≤5000),当然如果这个数是负的,那她的速度将是0.牛德比亚的高速会路法规定,在高速公路上行驶的车辆时速不得低于
/(1≤L≤1,000,000).那么,请你计算有多少奶牛可以在高速公路上行驶呢?
Input
Output
Sample Input
5
7
5
INPUT DETAILS:
There are three cows with one lane to drive on, a speed decrease
of 1, and a minimum speed limit of 5.
Sample Output
OUTPUT DETAILS:
Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.