题目描述

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

 

#include<cstdio>
int main()
{
	int N,M,dot1,dot2,SUM=0;
	int distance[100001];
	scanf("%d",&N);		
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&distance[i]);//存放距离,distance[1]表点1到点2的距离.... 
		SUM=SUM+distance[i];//存放总路程 
		
	}
	scanf("%d",&M);	
	for(int i=1;i<=M;i++)
	{
		int short_dis=0,floor,ceiling;
		scanf("%d%d",&dot1,&dot2);//存放距离,[0]表点1到点2.... 
		if(dot1<dot2) //谁大谁是上限,谁小谁是下限 
		{
			floor=dot1;
			ceiling=dot2;
		}
		else
		{
			ceiling=dot1;
			floor=dot2;
		}
		for(int j=floor;j<ceiling;j++)
			short_dis=short_dis+distance[j];
		if((SUM-short_dis)<short_dis)
			short_dis=SUM-short_dis;  
		printf("%d\n",short_dis);
		
	}
	return 0;
}

 

久违的说明:

哈哈...简直脑壳痛...倒不是题目翻译不过来...题目的表达像the i-th and the (i+1)-st 我就郁闷了好久...

最后索性直奔输入输出...才看懂原来就是简简单单的...和下一个点的距离...如果这个点是最后一个点...那就是和第一个点的距离...

 还真是a simple cycle...

题目要求就是:圈里n个点,求某两个点的最短路径

emm 第一反应就是循环链表...想了一分钟还会算了...改天再研究 

既然是一个圈里两点的距离...那就只有顺时针和逆时针两种走法

 

先顺便学两个单词

顺时针 Clockwise

逆时针 Anti-clockwise 或者counter-clockwise

 

按题目数据假设 a=1->2的距离 b=2->3 ....e=5->1

那1->3的路径 要么是 a+b 要么就是 c+d+e 简化一下即总距离-(1->3)的距离

还有就是像4->1这种怎么办...为了简化代码...只需要下面这样的一个判断就可以了...

		if(dot1<dot2) //谁大谁是上限,谁小谁是下限 
		{
			floor=dot1;
			ceiling=dot2;
		}
		else
		{
			ceiling=dot1;
			floor=dot2;
		}

 做之前的时候百度这题看了一下别人的代码..好像有吐槽说超时的...一个博主还po了超时的代码...看了一下codeup 时间限制: 1 Sec   心想应该不会吧  我提交了一下..还真得会超时..然后久违的自己边在博客写分析边写代码..写完提交..

最后也过了,并没有出现超时...然后回过头看那个超时的代码..循环太多..

所以厘清思路还是挺重要的(言外之意,写博客是很重要的 哈哈),.对于优化代码也是...

最后发现配套的书上其实也有这套题..代码比我写的还要精致不少..

连二重循环都没用到...两个循环搞定...读取的时候顺便做了一个数组dis[i] 存放1号点到i号点的顺时针距离..

 

突然想起小学课本,通往广场的路不止一条,又想想这道题不也是吗,顺时针和逆时针的路,你走的可能并不是最快的那一条

继续努力吧!

留给自己的时间不多了