【PAT】【Advanced Level】1046. Shortest Distance (20)

2024-06-17 04:32

本文主要是介绍【PAT】【Advanced Level】1046. Shortest Distance (20),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1046. Shortest Distance (20)

时间限制
100 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

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 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.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output:
3
10
7
原题链接:

https://www.patest.cn/contests/pat-a-practise/1046

思路:

每一位存累加和,然后计算两个方向

CODE:

#include<iostream>using namespace std;int main()
{int n;cin>>n;int sum[n+1];sum[0]=0;for (int i=1;i<=n;i++){cin>>sum[i];sum[i]+=sum[i-1];}int m;cin>>m;for (int i=0;i<m;i++){int a,b;cin>>a>>b;if (a>b)swap(a,b);cout<<min(sum[b-1]-sum[a-1],sum[a-1]-sum[0]+sum[n]-sum[b-1])<<endl;}return 0;
}


这篇关于【PAT】【Advanced Level】1046. Shortest Distance (20)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068486

相关文章

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

MiniCPM-V: A GPT-4V Level MLLM on Your Phone

MiniCPM-V: A GPT-4V Level MLLM on Your Phone 研究背景和动机 现有的MLLM通常需要大量的参数和计算资源,限制了其在实际应用中的范围。大部分MLLM需要部署在高性能云服务器上,这种高成本和高能耗的特点,阻碍了其在移动设备、离线和隐私保护场景中的应用。 文章主要贡献: 提出了MiniCPM-V系列模型,能在移动端设备上部署的MLLM。 性能优越:

【语句】如何将列表拼接成字符串并截取20个字符后面的

base_info = "".join(tree.xpath('/html/head/script[4]/text()'))[20:] 以下是对这个语句的详细讲解: tree.xpath('/html/head/script[4]/text()')部分: tree:通常是一个已经构建好的 HTML 文档树对象,它是通过相关的 HTML 解析库(比如 lxml)对 HTML 文档进行解

POJ 2001 Shortest Prefixes(字典树入门)

题目: http://poj.org/problem?id=2001 题意: 找到多个字符串中,各自唯一的最短子串,例如 carte 与 carce 各自唯一的最短子串为cart与carc,即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码: #include<stdio.h>#include<string>typedef str

C++20中支持的非类型模板参数

C++20中支持将类类型作为非类型模板参数:作为模板参数传入的对象具有const T类型,其中T是对象的类型,并且具有静态存储持续时间(static storage duration)。       在C++20之前,非类型模板参数仅限于:左值引用类型、整数类型、指针类型、指向成员类型的指针、枚举类型、std::nullptr_t。在C++20中,它已扩展并支持:浮点类型、字面量类类

Google 实现量子霸权!3分20秒运算,世界第一超算要跑1万年!

大数据技术与架构 点击右侧关注,大数据开发领域最强公众号! 暴走大数据 点击右侧关注,暴走大数据! By  大数据技术与架构 场景描述:谷歌宣称“量子霸权”已经实现,他们首次在实验中证明了量子计算机对于传统架构计算机的优越性:在世界第一超算 Summit 需

PAT甲级-1044 Shopping in Mars

题目   题目大意 一串项链上有n个钻石,输入给出每个钻石的价格。用m元买一个连续的项链子串(子串长度可为1),如果不能恰好花掉m元,就要找到最小的大于m的子串,如果有重复就输出多个,按递增顺序输出子串的前端和后端索引。 原来的思路 取连续的子串使和恰等于m,没有恰等于就找最小的大于。可以将子串依次累加,使得每个位置都是起始位置到该位置的序列和,整个数组显递增顺序,就可以用右边减左边

UI 自动化技能:20个实战技巧!测试工程师必看!

大家周五 好啊!忙碌了一周,又可以懒洋洋躺在沙发上了~~~ 又到了每年的金九银十了,今天聊聊如何提升UI自动化话题... 你是否在求职过程中感受到UI自动化的技能不足? 随着测试行业的发展,UI自动化测试已成为每位测试工程师的必修课。无论你是想提升现有的测试效率,还是在找工作中获得竞争优势,掌握UI自动化技能都能为你带来巨大的帮助。那么,如何快速提升这些技能呢? UI(用户界面)自