PAT A1046

news/2024/10/23 5:39:03/

思路:

1. 题意为输入点数以及点之间的距离,要求给出点对,输出点之间的最短距离。

2. 处理时确定点对的大小顺序,分别计算从小到大的和sum1,以及从大到小的和sum2,之后对两数进行比较,确定较小的数并输出。代码如下

#include<cstdio>
int a[100010];
int p1[10010];
int p2[10010];
int shortest_way(int n,int c,int b){int sum1=0,sum2=0,i;int low,high;low=c<b?c:b;high=c>b?c:b;for(i=low-1;i<high-1;i++){sum1+=a[i];}for(i=high-1;i<n;i++){sum2+=a[i];}for(i=0;i<low-1;i++){sum2+=a[i];}return sum1<sum2?sum1:sum2;
}
int main(){int N,i,M;scanf("%d",&N);for(i=0;i<N;i++){scanf("%d",&a[i]);}scanf("%d",&M);for(i=0;i<M;i++){scanf("%d%d",&p1[i],&p2[i]);}for(i=0;i<M;i++){printf("%d\n",shortest_way(N,p1[i],p2[i]));}
}

提交时第三个测试点出现超时现象,这里循环时间太大出现了超时,因此必须经过预处理,但不太清楚如何进行预处理,查看答案后发现,实例中为一个环,因此sum1和sum2之和为环的总长度,初始化时一定是要预先将查询值存在数组里面,在输入时进行预处理,确定一个点1,然后将1到个点的距离存储在数组中,查询i,j点时只需将数组中对应位置元素相减即可,在输出时确定两者之间的较小值。

总结:没有想到的原因是没有注意到整体结构是个圆环状,因此计算了两边的距离。此外,没有注意到可以将两点之间的距离转换为求一个确定点到两点之间的距离之差。


http://www.ppmy.cn/news/323935.html

相关文章

教你禁用mac笔记本的独立显卡

mac笔记本用户为了省电提高续航等情况&#xff0c;怎么禁用独立显卡&#xff0c;只使用核显呢&#xff1f; 可以使用mac自带的 pmset 电源管理命令&#xff0c;在终端输入以下命令&#xff1a; sudo pmset -b GPUSwitch 0 sudo pmset -c GPUSwitch 1命令含义&#xff1a; -c …

PAT A1086

#include <stdio.h> #include <string.h> #include <malloc.h> #define maxn 1010 typedef struct BST { struct BST *lchild, *rchild; int data; }*Bst; int n,pre[maxn],in[maxn],post[maxn]; Bst create(int preL,int preR,int inL,int inR)//已知前序&a…

PAT-A1126

前几天去刷了PAT&#xff0c;趁热把答案记录下来供大家参考 这题完全是英语阅读题&#xff0c;题目读懂就能写 我考试的时候花了起码10分钟去读题&#xff0c;英语实在太渣 第3个测试点是个坑点&#xff0c;考的时候提交了11次才出来 第3个测试点&#xff1a;关键字&#…

A1016(25)

很考察耐心的一道题&#xff0c;写起来也不是很复杂&#xff0c;耐心去做肯定是能写出来的啦 下面介绍一下auto的用法&#xff0c;比如&#xff0c;int或者double&#xff0c;我们可以写成&#xff0c;int i0&#xff1b;double k0.0&#xff0c;那么auto相当于我没有指代这个究…

PAT a1126

目的&#xff1a;判断是否是Eulerian Path 输入&#xff1a; 每个点 每个边 输出&#xff1a; 判断是哪种情况 算法&#xff1a; 用hash表统计每个点的度。如果全为偶数&#xff0c;则为Eulerian 如果有两个点的度为奇数&#xff0c;则为semi-Eulerian 如果不是以上的…

PAT A1128

AC代码如下 #include <iostream> #include <cmath>using namespace std;const int max_k210; int output[max_k]{0}; const int max_n1100; int queen[max_n]{0};bool is_solution(int n,int a[]){for(int i 0; i < n -1 ;i){for(int j i1 ; j < n ;j){if…

解决macbook pro在只有win8系统下开启AHCI的问题

背景&#xff1a; 我的macbook pro换了一块SSD&#xff0c;只安装了win8系统&#xff0c;但是因为没有开启AHCI导致系统速度严重降低&#xff0c;没错&#xff0c;是严重降低&#xff0c;因为macbook在os x系统下才会自动开启AHCI&#xff0c;所以下定决心搞定它。 所需工具&a…

A1066

没写出&#xff0c;平衡二叉树需要多练多思考多画图. 注意点&#xff1a; 1、有可能并不是根结点的左右子树未平衡&#xff0c;遇到这种情况时&#xff0c;做平衡操作后&#xff0c;需要让该节点的父亲结点指向更新后的孩子结点&#xff0c;以保证树中间不断掉. 通过它们实现&a…