题目大意：很多的蚂蚁都在长度为L（cm）的杆子上爬行，它们的速度都是1cm/s，到了棒子终端的时候，蚂蚁就会掉下去。如果在爬行途中遇到其他蚂蚁，两只蚂蚁的方向都会逆转。已知蚂蚁在棒子的最初位置坐标，但是我们不知道他们会往哪一个方向爬。请求出所有蚂蚁掉下去的最短时间和最长时间。
题目分析：虽然当蚂蚁数量很多的时候情况会有很多种，但是先考虑小数量的分析就可以找到解决方法：如果只有两只的话，那么最短时间就是两只蚂蚁距离两端点距离较小的距离中取大者就是所需最短时间，而最长时间就是两只蚂蚁距离两端点距离较大者中取大者就是所需最长时间，例如，长度为10，一只在距离左端2的位置，一只在距离左端6的位置，则最短时间为max(min(2,10-2),min(6,10-6))为4,最长时间为max((max(2,10-2),max(6,10-6)))为8其实就是两只相向而行，当相遇后，都转为逆向，则时间为从相遇点到端点距离大者与相遇前所需时间，分析实际就是2到10的距离，当蚂蚁数量增加时，情况相同。
则需要时间最长的的就是让距离端点最近的蚂蚁爬到另一个端点(最远)所需要的时间。
也就是说，只要找出所有蚂蚁与较远端比较，然后找出最大值就是所需要的最大时间。
这里需要注意的就是两只蚂蚁相遇转向的那个梗。事实上，可以知道两只蚂蚁相遇后，当他们保持原样交错而过继续前进也不会有任何问题。这样看来，可以认为每只蚂蚁都是独立运动的，所以要求最长时间，只要求蚂蚁到杆子端点的最大距离就好了。
#include <cstdio>
#include <iostream>
using namespace std;
int min_time, max_time;
int h, n, T, tmp;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d" , &h, &n);
min_time = 0;
max_time = 0;
for(int i=0;i<n;i++) {
scanf("%d", &tmp);
min_time = max(min_time, min(tmp, h - tmp));
max_time = max(max_time, max(tmp, h - tmp));
}
printf("%d %d\n", min_time, max_time);
}
return 0;
}
posted @
2015-02-11 15:09 JulyRina 阅读(239) |
评论 (0) |
编辑 收藏 其实刚开始参加ACM竞赛的时候一方面是兴趣，另一方面是感觉实验室都是一帮优秀的人。
所以即使不能拿到什么奖项，能够从这帮牛人里边学到一些东西，对我来说也已经获益匪浅。
国内每年会举办5场regional，14年开始涨到了6场。每场比赛都会有70所高校，而这些高校很多都集中在国内的一本的高校。
每场比赛都会有70所左右的高校，170支左右的队伍，而这些高校很多都集中在国内的一本高校。
当然也有二本和三本的院校。对我印象最深的是浙江大学城市学院，有过在final里面排名超过国内重点985院校的战绩。
但是搞ACM的人数远远超过reginal的名额。
因为比赛是三个人的，所以有的童鞋可能找不到好的队友。
或者因为别的一些原因而无缘regional。
虽然有时我也会觉得我们参加ACM的意义是什么？有时候我也觉得很迷茫。
但是我经常会有的想法是：我还是很喜欢ACM的，至少他让我的大学生活过的充实了许多，让我认识了很多志同道合的人。
当然，他也为我赢得了一些荣誉，让我学习到了很多东西。
除此之外，ACM的圈子是一个与学生会之流相比纯净的多的地方。我不希望有人带着什么坏思想来参加ACM，虽然我不知道别的竞赛是什么样的，但是我觉得如果你想要好好从事一项比赛，你就应该把它当做一个事业来看待。
ACM这项竞赛相对每个人来说其实是比较平等的。
大部分参加ACM竞赛的人在中学是没有接触过太多信息学竞赛的，但是事实证明他们通过大学的努力成为了大神，如：watashi。
ACM也不是重点高校的秀场，每个人都可以通过努力成为大神。
所以不要怀疑“我们学校ACM重来没进过regional，会不会。。。”之类的话，如果你真心想去一个地方，全世界都会给你让路。
所以，坚持自己的梦想吧，万一实现了呢：）
posted @
2015-02-11 14:51 JulyRina 阅读(131) |
评论 (0) |
编辑 收藏