UVA362 18,000 Seconds Remaining

题目描述

Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=298

PDF

输入格式

输出格式

输入输出样例 #1

输入 #1

100
10
20
20
0
10
0
10
0
10
0
20
200
60
30
100
10
50
5
5
5
5
25
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0

输出 #1

Output for data set 1, 100 bytes:
Time remaining: 4 seconds
Time remaining: 5 seconds
Total time: 11 seconds
Output for data set 2, 200 bytes:
Total time: 4 seconds
Output for data set 3, 50 bytes:
Time remaining: 1 seconds
Time remaining: stalled
Time remaining: stalled
Time remaining: 0 seconds
Total time: 20 seconds

---

Solution

大致题意

• 大多数计算机或软件在进行文件传输时会按照每隔 $5$ 秒的周期计算之前 $5$ 秒内传输的字节数，并以此推算传输文件的剩余部分需要多少秒（可以参考下图，图片来源网络）。

• 输入包含多组数据；

• 输入的每组数据首先是一个正整数 $n$ 表示文件大小，随后有若干个大于等于 $0$ 的整数表示某一秒内传输的大小，保证这些整数之和恰好等于文件大小。

• 每隔 $5$ 秒按照题目格式输出一次计算出的剩余时间（向上取整，单位是秒），如果某个连续的 $5$ 秒内 $1$ 个字节也没有传输，在相应的位置输出 stalled（n. 熄火，搁置，停滞）。

分析

1. 关于输入样例

题目的样例输入有些混乱，改写成下面的形式能够帮助大家理解。

100
10 20 20 0 10 0 10 0 10 0 20
200
60 30 100 10 50 5 5 5 5 25 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0

以样例中的第一组数据为例，总共 $100$ 字节的文件，最初的 $5$ 秒内总共传输了 $10+20+20+0+10=60$ 字节，由此计算出这 $5$ 秒内的平均速度是 $12\text{bytes/s}$。由于此时文件剩余 $100-60=40$ 字节，因此剩余的时间为 $40/12=3.33$ 秒，向上取整后输出预计剩余时间 $4$ 秒。在接下来的 $5$ 秒内，传输了 $0+10+0+10+0=20$ 字节，平均速度为 $4\text{bytes/s}$，由于文件剩余 $20$ 字节待传输，因此在这 $5$ 秒结束时输出剩余 $5$ 秒。最后一秒钟完成了最后 $20$ 字节的传输后，文件传输完毕，输出总共用时 $11$ 秒。

2. 最近的 $5$ 秒

根据题意，平均速度是由刚刚过去的 $5$ 秒内传输的字节数，除以 $5$ 来求得（注意：这里必须使用浮点数，虽然计算机领域很少说“$1.2$ 字节”这种话）。因此可以考虑使用双端队列滚动存储最近 $5$ 秒内的字节数，每输入一个新的数据，使用 push_back 将其放入队列，然后使用 pop 将队头（也就是 $6$ 秒前的过时数据）踢出去。参考代码：

while (remaining)
{
	cin >> x;
	bps.push_back(x);
    ...
	if (bps.size() >= 6) bps.pop_front();
    ...
}

3. 计时和剩余字节数

根据题意，计时操作伴随着文件的传输同步进行，因此在文件中每当读入一个值（表示某 $1$ 秒传输的字节数）后，时间值增加 $1$，剩余字节数（代码中用变量 remaining 表示，初始值为文件大小 filesize）减去对应的值。参考代码：

while (remaining)
{
	cin >> x;
    ...
	remaining -= x;
	totaltime += 1; 
    ...
}
...

4. 平均传输速率和预计剩余时间

将最近 $5$ 秒传输的字节数除以 $5.0$ 即为平均传输速率，剩余字节数除以平均速率，再使用 cmath 头文件里的函数 ceil 向上取整即可。由于是每 $5$ 秒更新一次预计剩余时间，因此需要在输出剩余时间前判断累计用时是够能够整除 $5$。参考代码：

bitsPer5second = 0; 
for (deque<int>::iterator it = bps.begin(); it != bps.end(); it += 1) bitsPer5second += *it;
if (totaltime % 5 == 0)
{
	if (bitsPer5second)printf("   Time remaining: %d seconds\n", (int)ceil(5.0 * remaining / bitsPer5second));
	else printf("   Time remaining: stalled\n");
}

5. 注意事项

一定！一定！一定！要按照题目要求输出（具体请参见 PDF 版的题面），需要注意的点包括：

1. Output for data set 多少 这一行，逗号后面有一个空格
   ，行末有一个冒号；
2. 每一个 Time remaining 的前面有 3 个空格（而不是一个制表符）；
3. Time remaining 和 Total time 的逗号后面有一个空格，冒号后面有一个空格；
4. Time remaining 和 Total time 的行末没有句点；
5. 一组数据完毕要输出一个空行。

代码

#include<iostream>
#include<deque>
#include<cmath>
#include<cstdlib>
using namespace std;

static void kernel() 
{
	static int filecnt = 1;
	int filesize, remaining, totaltime = 0, bitsPer5second, x;//文件大小, 剩余的大小和已用时间
	deque<int>bps;//滚动存储传输速率(某1秒内传输的字节数)
	cin >> filesize;
	if (filesize == 0) exit(0);
	remaining = filesize; 
	printf("Output for data set %d, %d bytes:\n", filecnt, filesize);
	while (remaining)
	{
		cin >> x;
		bps.push_back(x);
		remaining -= x;
		totaltime += 1; 
                //顶掉6秒前的数据，加入新的数据
		if (bps.size() >= 6) bps.pop_front();
		bitsPer5second = 0; 
		for (deque<int>::iterator it = bps.begin(); it != bps.end(); it += 1) bitsPer5second += *it;
		if (totaltime % 5 == 0)
		{
			if (bitsPer5second)printf("   Time remaining: %d seconds\n", (int)ceil(5.0 * remaining / bitsPer5second));
			else printf("   Time remaining: stalled\n");
		}//注意输出格式
	}
	printf("Total time: %d seconds\n", totaltime);
	cout << endl;//一组数据完毕输出一个空行
	filecnt += 1;
	return;
}

int main()
{
	while (1) kernel(); 
}

Extra

1. 当今大多数应用软件中，剩余时间/剩余字节数/已用时间/传输速率等信息会展示在 UI（用户界面）中，并且它们是并行计算，实时更新（而不是像题目一样依次更新）。本题的输出格式与命令提示符和 DOS 系统的输出行为非常类似。
2. 长时间 $1$ 个字节都没有传输是一件令人相当沮丧的事，出现此种情况时，题目中的 stalled 在有些系统上会显示为 N/A，在游戏平台 Steam 上会显示为“剩余时间超过 $1$ 年”（参见下图）。