{"id":586,"date":"2013-09-09T15:42:10","date_gmt":"2013-09-09T07:42:10","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=586"},"modified":"2013-09-09T15:42:10","modified_gmt":"2013-09-09T07:42:10","slug":"1046-shortest-distance-20","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=586","title":{"rendered":"1046. Shortest Distance (20)"},"content":{"rendered":"

\u65f6\u95f4\u9650\u5236\uff1a100ms
\nThe task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.
\nInput Specification:<\/b>
\nEach input file contains one test case. For each case, the first line contains an integer N (in [3, 105<\/sup>]), followed by N integer distances D1<\/sub>\u00a0D2<\/sub>\u00a0… DN<\/sub>, where Di<\/sub>\u00a0is the distance between the i-th and the (i+1)-st exits, and DN<\/sub>\u00a0is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104<\/sup>), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107<\/sup>.
\nOutput Specification:<\/b>
\nFor each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
\nSample Input:<\/b><\/p>\n

5 1 2 4 14 9\n3\n1 3\n2 5\n4 1<\/pre>\n
Sample Output:<\/b><\/p>\n
3\n10\n7<\/pre>\n
=============================================
\n\u6b64\u9898\u539f\u4ee5\u4e3a\u5f88\u7b80\u5355\uff0c\u521a\u60f3\u7591\u95ee\u4e3a\u5565PAT\u4e0a\u6b63\u786e\u7387\u5c310.2\u51e0….\u81ea\u5df1\u505a\u4e86\u624d\u53d1\u73b0\u539f\u6765\u4f1a\u8d85\u65f6\uff0c\u56e0\u4e3a\u6570\u636e\u91cf\u5f88\u5927\u3002
\n\u6700\u521d\u7684\u60f3\u6cd5\u8d85\u7ea7\u7b80\u5355\uff0c\u5c31\u662f\u8bb0\u5f55\u4e0b\u6bcf\u4e2a\u9876\u70b9\u95f4\u7684\u8ddd\u79bb\uff0c\u7b49\u5230\u6709\u67e5\u8be2\u7684\u65f6\u5019\u518d\u4e00\u4e2a\u4e2a\u8ba1\u7b97~\u7ed3\u679c\u5c3c\u739b\u7b2c\u4e09\u4e2a\u6d4b\u8bd5\u70b9\u59a5\u59a5\u7684\u8d85\u65f6\u4e86\uff01
\n\u80af\u5b9a\u662f\u7b97\u6cd5\u6709\u95ee\u9898\uff0c\u56e0\u4e3a\u7b97\u6cd5\u5b9e\u5728\u592a\u7b80\u5355\u4e86\u3002
\n\u540e\u6765\u561b\uff0c\u540e\u6765\u53bb\u7f51\u4e0a\u4e00\u641c\uff0c\u641c\u4e86\u4e00\u534a\u60f3\u5230\u4e24\u4e2a\u95ee\u9898\uff1a
\n1.\u6574\u4e2a\u5706\u5708\u7684\u603b\u957f\u5ea6\u77e5\u9053\u4e86\uff0c\u6211\u7b97\u51fa\u4e00\u8fb9\uff0c\u90a3\u4e48\u53e6\u4e00\u8fb9\u7684\u957f\u5ea6\u4e00\u51cf\u5c31\u51fa\u6765\u4e86
\n2.\u4ece\u70b9x\u5230\u70b9y\uff08\u5047\u8bbex\u5c0f\u4e8ey\uff09\u7684\u957f\u5ea6\uff0c\u4e0d\u5c31\u662f\u4ece 1\u5230y\u7684\u957f\u5ea6\u51cf\u53bb\u4ece1\u5230x\u7684\u957f\u5ea6\uff081\u70b9\u4e3a\u7b2c\u4e00\u4e2a\u70b9\uff09
\n  \u800c\u4ece1\u5230i\u7684\u957f\u5ea6\uff0c\u5176\u5b9e\u5728\u8bfb\u5165\u6570\u636e\u7684\u65f6\u5019\u4e0d\u5c31\u53ef\u4ee5\u8ba1\u7b97\u4e86!!!!!
\n
\ndist_sum[i] = dist[i-1] + currDist;
\n<\/code>
\n\u4e4b\u6240\u4ee5\u8fd9\u4e24\u79cd\u505a\u6cd5\u65f6\u95f4\u4e0a\u5dee\u522b\u90a3\u4e48\u591a\uff0c
\n\u56e0\u4e3a\u5e7c\u7a1a\u7684\u65b9\u6cd5\u91cc\u9762\uff0c\u6bcf\u6b21\u8ba1\u7b97\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u4e00\u5171M\u6b21\u67e5\u8be2\u5c31\u662fO(M*n)
\n\u73b0\u5728\u6bcf\u6b21\u67e5\u8be2\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(1)\uff0cM\u6b21\u67e5\u8be2\u4e5f\u5c31O(M)
\n\u9898\u76ee\u7ed9\u7684\u89c4\u6a21\uff0cn=100000, M=10000
\n\u5dee\u8ddd\u53ef\u60f3\u800c\u77e5~
\n=================================
\n
\n#include 
\nint getShortestDist(const int* dists, int N, int from, int to, long totalDist)
\n{
\n\tint dist_L, dist_R;
\n\tif(from > to)
\n\t{
\n\t\tint temp = from;
\n\t\tfrom = to;
\n\t\tto = temp;
\n\t}
\n\tdist_L = dists[to-1] - dists[from-1];
\n\tdist_R = totalDist - dist_L;
\n\treturn (dist_L<\/p>\n
\n\u6d4b\u8bd5\u70b9\t\u7ed3\u679c\t\u7528\u65f6(ms)\t\u5185\u5b58(kB)\t\u5f97\u5206\/\u6ee1\u5206\n0\t\u7b54\u6848\u6b63\u786e\t0\t780\t14\/14\n1\t\u7b54\u6848\u6b63\u786e\t0\t790\t3\/3\n2\t\u7b54\u6848\u6b63\u786e\t10\t1000\t3\/3\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u65f6\u95f4\u9650\u5236\uff1a100ms The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits. Input Specification: Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-586","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/586","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=586"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/586\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=586"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}