博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P3111 [USACO14DEC]牛慢跑Cow Jog_Sliver
阅读量:4692 次
发布时间:2019-06-09

本文共 690 字,大约阅读时间需要 2 分钟。

题目大意:n头牛在单行道n个位置,开始用不同的速度跑步。

当后面的牛追上前面的牛,后面的牛会和前面的牛以一样的速度

跑,称为一个小团体。问:ts后有多少个小团体。

题解:模拟

倒着扫一遍,因为某头牛后面的牛对这头牛的速度没影响。

计算出ts后牛的终点,如果能撞上前面最慢的牛,那么小团体数+1

注意开long long 

一开始不理解为什么倒着扫,

因为如果正着扫,看第i头牛能否撞上i+1头,

我们不确定第i+1头牛的速度,可能第i+1头牛

速度很快,追上i+2头牛速度减缓,从而被第i头牛追上。

代码:

#include
#include
#include
#define N 800009#define LL long longusing namespace std;LL n,t,ans,now;struct M{ LL p,v;}a[N];bool cmp(M a,M b){ return a.p
=1;i--){ if(a[i].p+a[i].v*t>=a[now].p+a[now].v*t)ans--; else now=i; } cout<
<
View Code

 

转载于:https://www.cnblogs.com/zzyh/p/7788215.html

你可能感兴趣的文章
MySQL 网络访问连接
查看>>
在aws ec2上使用root用户登录
查看>>
数据访问 投票习题
查看>>
CIO知识储备
查看>>
cnblog!i'm coming!
查看>>
使用点符号代替溢出的文本
查看>>
Axios 中文说明
查看>>
fatal: remote origin already exists.
查看>>
gridview 自定义value值
查看>>
2018二月实现计划成果及其三月规划
查看>>
类名.class和getClass()区别
查看>>
12/17面试题
查看>>
LeetCode 242. Valid Anagram
查看>>
JSP表单提交乱码
查看>>
如何适应现代雇佣关系
查看>>
团队项目(第五周)
查看>>
SQL 优化经验总结34条
查看>>
开源 视频会议 收藏
查看>>
核心J2EE模式 - 截取过滤器
查看>>
.net开源CMS
查看>>