6116 Problem E Shortest Distance (20)
質問E:Shortest Distance(20)
時間制限:1 Secメモリ制限:32 MB
タイトルの説明
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.
入力
Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 ... DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is 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), 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.
しゅつりょく
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
サンプル入力
サンプル出力
経験の総括
問題は、N個の出口間の距離を与え、M対出口を入力し、このM対出口間の最短距離を計算することを意味する.この問題は、出口ペアが与えられたときに2個の出口間の距離を順次加算することはできない.一般的に、クエリが存在する問題は静的クエリである.すなわち、クエリの結果は入力終了時にすでに得られたか、または簡易な計算を経て得られる.動的クエリーとは、クエリーの内容に基づいて計算を開始することであり、これまでデータの処理が行われていなかったことは明らかであり、動的クエリーはクエリーの数が多い場合にタイムアウトしやすいため、クエリーの問題が発生し、まずクエリーの入力から出力結果までの処理時間をできるだけ減らすべきである.
まず、各エッジを入力するときに、2つの量を計算します.1つはこのリングの総距離です.これは1つのsum累加で実現できます.もう1つは、最初の頂点が各頂点からの距離です.1次元配列で実現されます.各頂点の値は、入力した距離に1つの頂点を加えた値に等しく、最初は1という頂点の値を0に設定します.1から1自体が0なので.そして、入力された2つの頂点によって、それらと頂点1との距離を減算することで、そのうちの1つの距離が得られ、もう1つの距離はリングの総距離からこの距離を減算することで得られ、その後、2つの大きさを比較して、出力が最小になり、それからヽ( ̄▽ ̄)ノ
ACコード
時間制限:1 Secメモリ制限:32 MB
タイトルの説明
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.
入力
Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 ... DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is 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), 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.
しゅつりょく
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
サンプル入力
5 1 2 4 14 9
3
1 3
2 5
4 1
サンプル出力
3
10
7
経験の総括
問題は、N個の出口間の距離を与え、M対出口を入力し、このM対出口間の最短距離を計算することを意味する.この問題は、出口ペアが与えられたときに2個の出口間の距離を順次加算することはできない.一般的に、クエリが存在する問題は静的クエリである.すなわち、クエリの結果は入力終了時にすでに得られたか、または簡易な計算を経て得られる.動的クエリーとは、クエリーの内容に基づいて計算を開始することであり、これまでデータの処理が行われていなかったことは明らかであり、動的クエリーはクエリーの数が多い場合にタイムアウトしやすいため、クエリーの問題が発生し、まずクエリーの入力から出力結果までの処理時間をできるだけ減らすべきである.
まず、各エッジを入力するときに、2つの量を計算します.1つはこのリングの総距離です.これは1つのsum累加で実現できます.もう1つは、最初の頂点が各頂点からの距離です.1次元配列で実現されます.各頂点の値は、入力した距離に1つの頂点を加えた値に等しく、最初は1という頂点の値を0に設定します.1から1自体が0なので.そして、入力された2つの頂点によって、それらと頂点1との距離を減算することで、そのうちの1つの距離が得られ、もう1つの距離はリングの総距離からこの距離を減算することで得られ、その後、2つの大きさを比較して、出力が最小になり、それからヽ( ̄▽ ̄)ノ
ACコード
#include
int main()
{
int circle[100000],distance[100000];
distance[1]=0;
int n,m,sum=0;
scanf("%d",&n);
int b,e,low,high,dis1,dis2;
for(int i=1;i<=n;i++)
{
scanf("%d",&circle[i]);
sum+=circle[i];
distance[i+1]=distance[i]+circle[i];
}
scanf("%d",&m);
for(int j=0;je?b:e);
dis1=distance[high]-distance[low];
dis2=sum-dis1;
if(dis1