第二部分解題報(bào)告

1、Topcoder SRM 426 DiviLongStraightRoad解題I華東師范大學(xué)第二附屬中學(xué)【時(shí)空限制】每個(gè)測(cè)試點(diǎn)時(shí)限 2 秒，空間限制無。【問題描述】給出一些標(biāo)志，標(biāo)志的出現(xiàn)位置不確定但遞增。標(biāo)志上標(biāo)記有一些地點(diǎn)及它們距離此標(biāo)志的距離。地點(diǎn)名沒有重復(fù)。求出從最后一個(gè)標(biāo)志到某個(gè)目標(biāo)的地點(diǎn)的距離，如果輸入數(shù)據(jù)有或最后一個(gè)標(biāo)志的位置在目標(biāo)地點(diǎn)之后，則輸出無解?！緮?shù)據(jù)規(guī)模和約定】標(biāo)志數(shù) N50；不同的地點(diǎn)數(shù) M100。【試題】如果注意到，問題的各種條件限制都可以用如下形式表示，則問題的模型就清晰可辨：Pij=xj-xi=Qij其中 xi表示第 i 個(gè)元素的位置，元素可以是標(biāo)志也可以是地點(diǎn)

2、，P,Q 分別任兩個(gè)單位間的距離限制。顯然，如果 i,j 分別為有關(guān)聯(lián)的標(biāo)志和地點(diǎn)，則 Pi,j=Qi,j為對(duì)應(yīng)的距離；如果 均為標(biāo)志，則 （先考慮標(biāo)志必須非嚴(yán)格遞增的情形）。對(duì) 分開考慮，得到兩個(gè)典型的差分約束系統(tǒng)模型。只是，在本題中，并非只求出 的一組解即可，必須確定兩個(gè)元素的差是否為定值。為此，以 為例，定義 為的上界的最小值，初始有 。注意到對(duì)任意 均 有xj-xi=xk-xi+xj-xk=diff_Qi,k+diff_Qk,j由 為 上界 ， 。從而想到可以用 算法求得 的最小值，此值即 的 最大值。這就完成了對(duì) 系統(tǒng)的處理。同理可以完成對(duì) 系統(tǒng)的處理，求得 的最大值，即 的最小值。

3、顯然，如果存在任意 ，使得 ，返回異常值。對(duì)于標(biāo)志嚴(yán)格遞增的處理方法也很顯然了，如果兩標(biāo)志 ，有 ，則返回異常值。最后，末尾標(biāo)志（設(shè)為 ）和目標(biāo)地點(diǎn)（設(shè)為 ）之間距離的最大值和最小值。如果 ，則兩點(diǎn)距離不確定，返回異常值；如果 ， 則目標(biāo)地點(diǎn)已經(jīng)過，返回異常值；否則返回 為的距離。【算法描述】任兩點(diǎn)（標(biāo)志或地點(diǎn)）距離差的范圍。用 算法求得最大最小值，判斷不合法情況，最后即求得所需結(jié)果。點(diǎn)數(shù)為 ，故算法的總時(shí)間復(fù)雜度為 ?！酒渌惴ā客瓿缮鲜鲱}解后，經(jīng)過探索與交流，尚沒有發(fā)現(xiàn)或了解本題的其他算法?！緦?shí)現(xiàn)情況】實(shí)現(xiàn)情況【感謝】感謝 Olexiy 和StevieT 在 topcoder上提供的題解；

4、感謝 pashka 在比賽中完成的標(biāo)準(zhǔn)程序?！靖戒洝吭}Problem SementYou are driving on a long, straight road, on your way to a place whose name is given in destination. After awhile, you lose track of how far youve driven and realizet you may even have driven past yourdestination without noticing. t worry! says your friend,

5、who ishe car with you, I have an excellentmemory and can remember not only what was written on every road signsed, but alsowhat order they were in. Lets continue until we see the next road sign and maybe well be able to work outhow far we still have to go. You agree to his plan, butt quite trust his

6、 memory as much as he clearlydoes. You decidet youll be ve what he says as long as it is entirely consistent, otherwise youll try tofind somewheret you can buy a map.The information written on each sign is a semi-colon separated list, where each element of the list is thename of a place and the dist

7、ance tot place from the sign separated by a space. For exle, if sign icontained A 10;B 15 (quotes for clarity) and the sign were located a distance of Si units down the road,then the place called A would be located PA = Si + 10 units down the road and the place called B would be located PB = Si + 15

8、 units down the road. The distanwill never be negative, so only plat areeast as far along the road as the sign can be listed. Notet the values in S and P need notbeegers andt plawill have distinct names. You are given the information written on sign i as yourfriend remembers it in signsi. Your frien

9、d claims to remember the order of the signs too, so if you wrotedown the values of Si for each sign, they would be in strictly increasing order (no two signs were colocated).You are currently at the sameition as the sign givenhe lasement of signs. If the information givenin signs is consistent, you

10、can determine the remaining distance to your destination and this distance isnon-negative, then return this distance. Otherwise, if there is no wayt the data given in signs couldrepresent a set of signs and pladestination from the information instead.as descr bed above, or you cannot determine the d

11、istance to yourhe signs, or you have already driven past your destination, return -1DefinitionClass:LongStraightRoadMethod:distanceToDestinationParameters:String, StringReturns:Method signature:distanceToDestination(String signs, String destination)(be sure your method is public)Notes- While no two

12、signs were at the sameition on the road, plamay be legitimay colocated with otherplaand with the signs.Constras-A place is a string containing beten 1 and 50 uppercase letters (A - Z), inclusive.A distance is aneger betn 0 and 10000, inclusive, formatted without leading zeros.signs will contain betn

13、 1 and 50 elements, inclusive.Each element of signs will contain betn 1 and 50 characters, inclusive.Each element of signs will be a semicolon-separated list, each item of which will be a place and a distance,separated by a space.-No element of signs will contahe same place moren once.signs will con

14、tain no moren 100 distinct pladestination will be a place.Exles0)COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13,MARLBOROUGH 2GLASTONBURYReturns: 14Thesignls yout GLASTONBURY is 12 units furthern MARLBOROUGH. Since youre now 2units from MARLBOROUGH, you must be 14 units from GLASTONBURY.1)COLCHESTER 5;GL

15、ASTONBURY 25;MARLBOROUGH 13,GLASTONBURY 13;MARLBOROUGH 2GLASTONBURYReturns: -1The distance betn GLASTONBURY and MARLBOROUGH has changed betn theand secondsigns, so theyre inconsistent. Even though you are standing next to a signfrom your destination, return -1.tls us how far you are2)A 25;B 15,A 2BR

16、eturns: -1Youve driven past your destination by 8 units.3)YVO 60;J 62,K 45,K 40;MV 17,K 37;YVO 44;HY 48;CC 69;D 77;YXF 80,YVO 30;B 37;RB 59MVReturns: 0Youre standing righyour destination.4)A 200;B 150,C 45;D 100;E 150,C 25;E 130,F 80;G 65,G 35;H 160,A 160,H 130FReturns: -1There is no way the signs c