题目描述
高速公路上有N(1<=N<=50,000)只奶牛，编号为1..N,每头牛都开着自己的车，第i头牛的车速为S_i(1<=S_i<=1,000,000)km/h，告诉公路上一共有M个车道(1<=M<=N)。
为了安全起见，每头牛都遵循以下原则：同车道前面有x头牛，牛的车速就会降低D*X(0<=D<=5,000)KM/h，当然不会降到0以下，所以车速应该max(S_i-D*X,0)。由于车距很大，所以即使后面的车比前面的车快，你也不用担心会发生碰撞。
高速公路上有一个最低限速L(1<=L<=1,000,000),凡是低于该速度的车不允许上高速，现在请你来计算一共可以多少辆车在高速公路上行驶。
输入
第1行: 4个空格隔开的整数N,M,D,L
第2..N+1行: 第i+1行描述第i头牛的起初车速。
输出
第一行: 输出一个整数表示最多可以在高速上行驶的牛车数量。
思路
贪心，先把速度从小到大排序；用数组f来记录这一条车到上已经有的数量，如果能放就把速度最小的那个依次放入，只用累加f和答案就可以了‘
#include#include #include long long s[50000]; long long f[50000]; int i,j,k; long long n,m,d,l,ans; using namespace std; int main() { scanf("%d%d%d%d",&n,&m,&d,&l); for (i=1;i<=n;i++) scanf("%d",&s[i]); sort(s,s+n+1); for (j=1;j<=n;j++) { for (i=1;i<=m;i++) { if (s[j]-d*f[i]>=l) { f[i]++; ans++; break; } } } printf("%d",ans); return 0; }
]]>
Comments NOTHING