題目大意：很多的螞蟻都在長(zhǎng)度為L(zhǎng)（cm）的桿子上爬行，它們的速度都是1cm/s，到了棒子終端的時(shí)候，螞蟻就會(huì)掉下去。如果在爬行途中遇到其他螞蟻，兩只螞蟻的方向都會(huì)逆轉(zhuǎn)。已知螞蟻在棒子的最初位置坐標(biāo)，但是我們不知道他們會(huì)往哪一個(gè)方向爬。請(qǐng)求出所有螞蟻掉下去的最短時(shí)間和最長(zhǎng)時(shí)間。
題目分析：雖然當(dāng)螞蟻數(shù)量很多的時(shí)候情況會(huì)有很多種，但是先考慮小數(shù)量的分析就可以找到解決方法：如果只有兩只的話，那么最短時(shí)間就是兩只螞蟻距離兩端點(diǎn)距離較小的距離中取大者就是所需最短時(shí)間，而最長(zhǎng)時(shí)間就是兩只螞蟻距離兩端點(diǎn)距離較大者中取大者就是所需最長(zhǎng)時(shí)間，例如，長(zhǎng)度為10，一只在距離左端2的位置，一只在距離左端6的位置，則最短時(shí)間為max(min(2,10-2),min(6,10-6))為4,最長(zhǎng)時(shí)間為max((max(2,10-2),max(6,10-6)))為8其實(shí)就是兩只相向而行，當(dāng)相遇后，都轉(zhuǎn)為逆向，則時(shí)間為從相遇點(diǎn)到端點(diǎn)距離大者與相遇前所需時(shí)間，分析實(shí)際就是2到10的距離，當(dāng)螞蟻數(shù)量增加時(shí)，情況相同。
則需要時(shí)間最長(zhǎng)的的就是讓距離端點(diǎn)最近的螞蟻爬到另一個(gè)端點(diǎn)(最遠(yuǎn))所需要的時(shí)間。
也就是說(shuō)，只要找出所有螞蟻與較遠(yuǎn)端比較，然后找出最大值就是所需要的最大時(shí)間。
這里需要注意的就是兩只螞蟻相遇轉(zhuǎn)向的那個(gè)梗。事實(shí)上，可以知道兩只螞蟻相遇后，當(dāng)他們保持原樣交錯(cuò)而過(guò)繼續(xù)前進(jìn)也不會(huì)有任何問(wèn)題。這樣看來(lái)，可以認(rèn)為每只螞蟻都是獨(dú)立運(yùn)動(dòng)的，所以要求最長(zhǎng)時(shí)間，只要求螞蟻到桿子端點(diǎn)的最大距離就好了。
#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 閱讀(257) |
評(píng)論 (0) |
編輯 收藏 其實(shí)剛開(kāi)始參加ACM競(jìng)賽的時(shí)候一方面是興趣，另一方面是感覺(jué)實(shí)驗(yàn)室都是一幫優(yōu)秀的人。
所以即使不能拿到什么獎(jiǎng)項(xiàng)，能夠從這幫牛人里邊學(xué)到一些東西，對(duì)我來(lái)說(shuō)也已經(jīng)獲益匪淺。
國(guó)內(nèi)每年會(huì)舉辦5場(chǎng)regional，14年開(kāi)始漲到了6場(chǎng)。每場(chǎng)比賽都會(huì)有70所高校，而這些高校很多都集中在國(guó)內(nèi)的一本的高校。
每場(chǎng)比賽都會(huì)有70所左右的高校，170支左右的隊(duì)伍，而這些高校很多都集中在國(guó)內(nèi)的一本高校。
當(dāng)然也有二本和三本的院校。對(duì)我印象最深的是浙江大學(xué)城市學(xué)院，有過(guò)在final里面排名超過(guò)國(guó)內(nèi)重點(diǎn)985院校的戰(zhàn)績(jī)。
但是搞ACM的人數(shù)遠(yuǎn)遠(yuǎn)超過(guò)reginal的名額。
因?yàn)楸荣愂侨齻€(gè)人的，所以有的童鞋可能找不到好的隊(duì)友。
或者因?yàn)閯e的一些原因而無(wú)緣regional。
雖然有時(shí)我也會(huì)覺(jué)得我們參加ACM的意義是什么？有時(shí)候我也覺(jué)得很迷茫。
但是我經(jīng)常會(huì)有的想法是：我還是很喜歡ACM的，至少他讓我的大學(xué)生活過(guò)的充實(shí)了許多，讓我認(rèn)識(shí)了很多志同道合的人。
當(dāng)然，他也為我贏得了一些榮譽(yù)，讓我學(xué)習(xí)到了很多東西。
除此之外，ACM的圈子是一個(gè)與學(xué)生會(huì)之流相比純凈的多的地方。我不希望有人帶著什么壞思想來(lái)參加ACM，雖然我不知道別的競(jìng)賽是什么樣的，但是我覺(jué)得如果你想要好好從事一項(xiàng)比賽，你就應(yīng)該把它當(dāng)做一個(gè)事業(yè)來(lái)看待。
ACM這項(xiàng)競(jìng)賽相對(duì)每個(gè)人來(lái)說(shuō)其實(shí)是比較平等的。
大部分參加ACM競(jìng)賽的人在中學(xué)是沒(méi)有接觸過(guò)太多信息學(xué)競(jìng)賽的，但是事實(shí)證明他們通過(guò)大學(xué)的努力成為了大神，如：watashi。
ACM也不是重點(diǎn)高校的秀場(chǎng)，每個(gè)人都可以通過(guò)努力成為大神。
所以不要懷疑“我們學(xué)校ACM重來(lái)沒(méi)進(jìn)過(guò)regional，會(huì)不會(huì)。。。”之類的話，如果你真心想去一個(gè)地方，全世界都會(huì)給你讓路。
所以，堅(jiān)持自己的夢(mèng)想吧，萬(wàn)一實(shí)現(xiàn)了呢：）
posted @
2015-02-11 14:51 JulyRina 閱讀(145) |
評(píng)論 (0) |
編輯 收藏