UVA 10714 Ants (贪心）

本文主要是介绍UVA 10714 Ants (贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

10714 - Ants Time limit: 3.000 seconds

题意： 一根n厘米的杆子上，有m只蚂蚁，蚂蚁爬行速度为1厘米/秒。每只蚂蚁在一个位置上，可能向左爬也可能向右边爬。如果两只蚂蚁碰头，则两只蚂蚁都转向。如果蚂蚁爬到杆边就脱落了。现在要求出所有蚂蚁脱落的最小和最大时间。

思路: 其实这题说是两只蚂蚁碰头，两只蚂蚁都转向。其实这是一个误导人的条件。。设想一下：两只蚂蚁碰头转向和继续向前爬有区别吗？。比如蚂蚁A向右蚂蚁B向左。碰头后应该是蚂蚁A向左蚂蚁B向右。但是每只蚂蚁速度都一样。所以蚂蚁A和蚂蚁B其实可以看成同样的蚂蚁。所以碰头后可以看成蚂蚁A仍向右。蚂蚁B仍向左。。

知道这一点后。这题就完全是水题了。。

找出最小的时间：每只蚂蚁都往最近的杆边爬。即杆左边的往左边爬，杆右边的往右边爬。。这样时间最小。

找出最大的时间：每只蚂蚁都往最远的杆边爬。即杆左边的往右边爬，杆右边的往左边爬。。这样时间最大。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int t;
int n, m;
int Min, Max;
int num[1000005];int main() {scanf("%d", &t);while (t --) {scanf("%d%d", &n, &m);Min = 0;for (int i = 0; i < m; i ++) {scanf("%d", &num[i]);if (2 * num[i] < n) Min = max(Min, num[i]);else Min = max(Min, n - num[i]);}sort(num, num + m);Max = max(n - num[0], num[m - 1]);printf("%d %d\n", Min, Max);}return 0;
}

这篇关于UVA 10714 Ants (贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---