poj 1852 Ants 排序

缘起

poj 1852 Ants 智力题（适合面试）

分析

题意很裸

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
一队蚂蚁在长度为1厘米的水平杆上行走，每根杆的速度恒定为1厘米/秒。 当一只行走的蚂蚁到达极的一端时，它会立即从
它上掉下来。 当两只蚂蚁相遇时，它们会转身并开始向相反方向行走。 我们知道蚂蚁在杆子上的原始位置，不幸的是，我
们不知道蚂蚁行走的方向。 你的任务是计算所有蚂蚁从杆上掉下来所需的最早和最晚时间。

【输入】
第一行输入包含一个整数，给出后面的案例数。 每种情况的数据都以两个整数开始：杆子长度（cm）和n，极点上的蚂蚁数
量。 这两个数字之后是n个整数，它们将杆上每只蚂蚁的位置作为从杆的左端测量的距离，没有特别的顺序。 所有输入整数都不大于1000000，它们由空格分隔。

【输出】
对于每种输入情况，输出由单个空格分隔的两个数字。 第一个数字是所有蚂蚁从杆上掉下来的最早时间（如果他们的步行
方向选择得恰当），第二个数字是最晚可能的时间。

【样例输入】
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

【样例输出】
4 8
38 207

【限制】
Time limit 1000 ms
Memory limit 30000 kB

题目的意思是, 如果合理调配这n只蚂蚁一开始的运行方向，则要输出所有蚂蚁都掉下杆子的最长时间和最短时间.

如果没想到思路，用模拟的话，会死人的~ 估计每个几百行是打不住的. 但是想到了的话就太简单了——20行足以. 其实本题的核心思路是两只蚂蚁相遇掉头，其实因为蚂蚁和蚂蚁是没有区别的——我们完全可以视作这两只蚂蚁穿过了彼此——所以其实这n只蚂蚁彼此没有关系，所以只需要求出每只蚂蚁要掉下去的最短时间和最长时间形成2个数组，然后快排即可

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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;

int a[maxn], b[maxn],L,n,d,top; // a存储每只蚂蚁掉落杆子的最长时间 b存储最短时间

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		top = 0;
		scanf("%d%d", &L, &n);
		while(n--)
		{
			scanf("%d", &d);
			a[top] = max(d, L-d);
			b[top] = min(d, L-d);
			top++;
		}
		sort(a, a+top);
		sort(b, b+top);
		printf("%d %d\n", b[top-1], a[top-1]); // 最快时间是n只蚂蚁的最快时间的最大值(因为需要所有蚂蚁都掉下去, 所以要取最大)
	}
	return 0;
}

ac情况

Status Accepted
Time 204ms
Memory 912kB
Length 528
Lang C++
Submitted 2019-08-15 14:33:30
Shared
RemoteRunId 20743515

后面发现自己傻逼了~ 根本不需要排序好不好? 就求个最大值最小值要排什么序呢? 我硬生生的把O(N)的算法搞成了O(nlogn)的了, 而且空间复杂度完全不需要那么高~

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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#include <algorithm>
using namespace std;

int L,n,d;

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int _max = -1, _min = -1;
		scanf("%d%d", &L, &n);
		while(n--)
		{
			scanf("%d", &d);
			_max = max(_max, max(d,L-d));
			_min = max(_min, min(d,L-d));
		}
		printf("%d %d\n", _min, _max);
	}
	return 0;
}

ac情况

Status Accepted
Time 125ms
Memory 112kB
Length 434
Lang C++
Submitted 2019-08-15 14:39:27
Shared
RemoteRunId 20743581

速度快了一倍，空间减少了近9倍