Ants

A POJ algorithm competition topic.

Posted by Dusign on 2019-11-12
Words 363 and Reading Time 1 Minutes
Viewed Times

Algorithms change the world. The importance of algorithms is self-evident to a programmer, so the practice of some algorithms is indispensable. Next, I will share some algorithmic problems.

Question

ants

Analysis

看到本题,很容易想到的是穷竭搜索,但是如果蚂蚁数量大的话穷竭搜索时间复杂度太大。仔细分析本题发现如果两只蚂蚁相遇之后各自掉头也可以看成两只蚂蚁交错通过,这对于结果没有什么影响,利用这一发现可以很容易的解决此问题。

Solution

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
36
37
38
39
40
41
42
43
44
45
46
47
//
// ants.cpp
// ANTS
//
// Created by dusign on 2019/11/16.
// Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>

using namespace std;

const int MAP_SIZE = 10000;

int max(int a, int b){
int tmp = a;
if(b > a)
tmp = b;
return tmp;
}

int min(int a, int b){
int tmp = a;
if(b < a)
tmp = b;
return tmp;
}

void solve(int L, int n, int *x){
int minT = 0, maxT = 0;
for(int i = 0; i < n; i++){
minT = max(minT, min(x[i], (L - x[i])));
maxT = max(maxT, max(x[i], (L - x[i])));
}
cout << minT <<endl;
cout << maxT <<endl;
}

int main(){
int L, n, x[MAP_SIZE];

cin >> L >> n;
for(int i = 0; i < n; i ++){
cin >> x[i];
}
solve(L, n, x);
}

Remark

解决一些算法问题时,要先想一想能不能用数学的思维简化问题,这样有时候会得到事半功倍的效果。就像是本题,如果使用穷竭搜索,不仅费时费力,而且时间复杂度也不理想。


If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

...

00:00
00:00