1623: [Usaco2008 Open]Cow Cars 奶牛飞车
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 386 Solved: 266
[Submit][Status][Discuss]
Description
编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰.高速公路有M(1≤M≤N)条车道.奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000).
在经历过糟糕的驾驶事故之后,奶牛们变得十分小心,避免碰撞的发生.每条车道上,如果某一只奶牛i的前面有K只奶牛驾车行驶,那奶牛i的速度上限就会下降K*D个单位,也就是说,她的速度不会超过Si – kD(O≤D≤5000),当然如果这个数是负的,那她的速度将是0.牛德比亚的高速会路法规定,在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000).那么,请你计算有多少奶牛可以在高速公路上行驶呢?
Input
第1行输入N,M,D,L四个整数,之后N行每行一个整数输入Si.
N<=50000
Output
输出最多有多少奶牛可以在高速公路上行驶.
Sample Input
3 1 1 5//三头牛开车过一个通道.当一个牛进入通道时,它的速度V会变成V-D*X(X代表在它前面有多少牛),它减速后,速度不能小于L
5
7
5
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
2
OUTPUT DETAILS:
Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.
思路:贪心。尽可能让这些车均匀分布。 以及初始就干掉那些最大速度小于L的。然后按照s[i]从小到大排序,先放置速度小的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
/* *********************************************** Author :111qqz Created Time :2016年04月04日 星期一 02时26分34秒 File Name :code/bzoj/1623.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=5E4+7; int n,m; int s[N]; int D,L; int num[N]; //num[i]表示第i个车道现在的有多少辆车 int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif ios::sync_with_stdio(false); cin>>n>>m>>D>>L; int cnt = 0 ; int total = n ; for ( int i = 0;i < n ; i++) { int x; cin>>x; if (x>=L) { s[cnt++] = x; } } int sad = n-cnt; n = cnt; sort(s,s+n); ms(num,0); for ( int i = 0 ; i < n ; i++) { int sp; sp = s[i]-num[i%m]*D; if (sp>=L) { num[i%m]++; } else sad++; } cout<<total-sad<<endl; #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!