文档章节

poj 1922 Ride to School

locusxt
 locusxt
发布于 2014/11/29 18:46
字数 514
阅读 37
收藏 0
Ride to School
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 19512 Accepted: 7878

Description

Many graduate students of Peking University are living in Wanliu Campus, which is 4.5 kilometers from the main campus – Yanyuan. Students in Wanliu have to either take a bus or ride a bike to go to school. Due to the bad traffic in Beijing, many students choose to ride a bike. 

We may assume that all the students except "Charley" ride from Wanliu to Yanyuan at a fixed speed. Charley is a student with a different riding habit – he always tries to follow another rider to avoid riding alone. When Charley gets to the gate of Wanliu, he will look for someone who is setting off to Yanyuan. If he finds someone, he will follow that rider, or if not, he will wait for someone to follow. On the way from Wanliu to Yanyuan, at any time if a faster student surpassed Charley, he will leave the rider he is following and speed up to follow the faster one. 

We assume the time that Charley gets to the gate of Wanliu is zero. Given the set off time and speed of the other students, your task is to give the time when Charley arrives at Yanyuan. 

Input

There are several test cases. The first line of each case is N (1 <= N <= 10000) representing the number of riders (excluding Charley). N = 0 ends the input. The following N lines are information of N different riders, in such format: 

Vi [TAB] Ti 

Vi is a positive integer <= 40, indicating the speed of the i-th rider (kph, kilometers per hour). Ti is the set off time of the i-th rider, which is an integer and counted in seconds. In any case it is assured that there always exists a nonnegative Ti. 

Output

Output one line for each case: the arrival time of Charley. Round up (ceiling) the value when dealing with a fraction.

Sample Input

4
20	0
25	-155
27	190
30	240
2
21	0
22	34
0

Sample Output

780
771

Source

Beijing 2004 Preliminary@POJ

写了init,但是忘记调用了。。。
可能一开始精度也有问题,是要尽量要用double float么?
discuss里面,有人说先乘后除精度损失少,这是什么原理呢。。


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10005

double len = 4.5;
double arrive_time[MAXN];
int num = 0;

void init()
{
	memset(arrive_time, 0, sizeof(arrive_time));
	num = 0;
}

int main()
{
	int n = 0;
	double vi = 0, ti = 0;
	while (true)
	{
		scanf("%d", &n);
		if (n == 0)
			break;
		init();
		for (int i = 0; i < n; ++i)
		{
			scanf("%lf%lf", &vi, &ti);
			if (ti < 0)
				continue;
			double tmp = 3600 * len / vi;
			arrive_time[num++] = ti + tmp;
		}

		double tmp = 100000000;
		for (int i = 0; i < num; ++i)
		{
			if (arrive_time[i] < tmp)
			{
				tmp = arrive_time[i];
			}
		}

		printf("%d\n", (int)(ceil(tmp)));
	}
	return 0;
}



© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
POJ ~ 1922 ~ Ride to School (思维)

题意:起点与终点相隔4.5公里。现Charley需要从起点骑车到终点。但是,他有个习惯,沿途需要有人陪伴,即以相同的速度, 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时,他会以相应...

zscdst
2018/04/14
0
0
hduoj题目分类

基础题:1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1...

hlearning
2014/02/25
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
160
1
POJ 3085 -- Quick Change

Quick Change Description J.P. Flathead’s Grocery Store hires cheap labor to man the checkout stations. The people he hires (usually high school kids) often make mistakes making......

小碧
03/28
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx访问日志/日志切割/静态文件过期时间/防盗链

Nginx访问日志主要记录部署在nginx上的网站访问数据,日志格式定义在nginx主配置文件中。 nginx主配置文件:/etc/nginx/nginx.conf 查看nginx主配置文件: ```markup [root@linux ~]# cat /e...

asnfuy
3分钟前
0
0
JS_高程4.变量,作用域和内存问题(2)执行环境及作用域

本文转载于:专业的前端网站➨JS_高程4.变量,作用域和内存问题(2)执行环境及作用域 1.执行环境:执行环境定义了变量或函数有权访问的其他数据,决定了它们各自的行为,       每个执...

前端老手
7分钟前
2
0
手机迅雷下载的文件,电脑上找不到问题

不知道手机迅雷怎么做到的,手机迅雷下载的文件,手机上可以看的到 但连电脑后, 电脑上看不到文件 . 尝试了打开查看隐藏文件, 但没有效果 . 手机上查询文件权限 也是对的 . 可读,可写, 不隐藏 ...

ol_O_O_lo
9分钟前
2
0
python学习11:Python tuple元组详解

元组是 Python 中另一个重要的序列结构,和列表类似,也是由一系列按特定顺序排序的元素组成。和列表不同的是,列表可以任意操作元素,是可变序列;而元组是不可变序列,即元组中的元素不可以...

太空堡垒185
21分钟前
3
0
Java实现数据结构之线性结构

一、顺序表 顺序表本质是使用数组储存数组的一种数据结构,在计算机的储存中是连续的分配内存的。 下面是我自己使用java实现的简单顺序表结构 package list; public class MyArrayList<E> { ...

daxiongdi
24分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部