[USACO08OPEN]牛的车Cow Cars
题目描述
N (1 <= N <= 50,000) cows conveniently numbered 1..N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 <= M <= N) and can travel at a maximum speed of S_i (1 <= S_i <= 1,000,000) km/hour.
After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 <= D <= 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max[S_i - D * K, 0]. While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as
described,
Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 <= L <= 1,000,000) km/hour so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.
编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰.高速公路有M(1≤M≤N)条车道.奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000).
在经历过糟糕的驾驶事故之后,奶牛们变得十分小心,避免碰撞的发生.每条车道上,如果某一只奶牛i的前面有南只奶牛驾车行驶,那奶牛i的速度上限就会下降kD个单位,也就是说,她的速度不会超过Si – kD(O≤D≤5000),当然如果这个数是负的,那她的速度将是0.牛德比亚的高速会路法规定,在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000).那么,请你计算有多少奶牛可以在高速公路上行驶呢?
输入输出格式
输入格式:
Line 1: Four space-separated integers: N, M, D, and L
- Lines 2..N+1: Line i+1 describes cow i's initial speed with a single integer: S_i
输出格式:
- Line 1: A single integer representing the maximum number of cows that can use the highway
输入输出样例
说明
There are three cows with one lane to drive on, a speed decrease of 1, and a minimum speed limit of 5.
Two cows are possible, by putting either cow with speed 5 first and the cow with speed 7 second.
思路
从小到大排序,然后贪心选择车道;
代码
#include<cstdio>
#include<algorithm>
#define LL long long
const int maxn=1e5+;
LL n,m,ans;
struct nate{LL t,d;}s[maxn];
bool comp(nate x,nate y){return x.t*y.d<x.d*y.t;}
int main(){
scanf("%lld",&n);
for(int i=;i<=n;i++){
scanf("%lld%lld",&s[i].t,&s[i].d);
s[i].t*=,m+=s[i].d;
}
std::sort(s+,s+n+,comp);
for(int i=;i<=n;i++){
m-=s[i].d;
ans+=s[i].t*m;
}
printf("%lld\n",ans);
return ;
}
最新文章
- django模板里循环变量<;table>;里想要两个一行如何控制
- Codevs 1860 最大数 string大法好,STL万岁。。
- mac os x安装ngigx+php fastcgi+mysql+memcache详细流程
- ***百度统计图表Echarts的php实现类,支持柱形图、线形图、饼形图
- Linux音频编程指南
- 【转】基于RSA算法实现软件注册码原理初讨
- centos7配置ip
- Appium python自动化测试系列之移动自动化测试前提(一)
- Nginx配置二级目录/路径 映射不同的反向代理和规避IP+端口访问
- Mac安装python3.x+pycharm+elasticsearch+常见报错处理(1)
- 背水一战 Windows 10 (93) - 选取器: FileOpenPicker, FolderPicker, FileSavePicker
- 使用select正确处理EOF的str_cli函数
- 如何看待淘宝二手交易APP“闲鱼”推出的新功能“闲鱼小法庭”?
- 1、Shiro 安全框架与Spring 整合详解
- 接口app 接口中上传 图片
- WEKA结果解读
- H5 以及 CSS3
- 监听home键+模拟home键
- Maximum Submatrix &; Largest Rectangle
- 从零开始,跟我一起做jblog项目(二)Maven