題目大意：很多的螞蟻都在長度為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 閱讀(249) |
評論 (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 閱讀(139) |
評論 (0) |
編輯 收藏