首页 > 代码库 > 绝对值最小
绝对值最小
题目描述:
给你一个数组A[n],请你计算出ans=min(|A[i]+A[j]|)(0<=i,j<n). 例如:A={1, 4, -3}, 则: |A[0] + A[0]| = |1 + 1| = 2. |A[0] + A[1]| = |1 + 4| = 5. |A[0] + A[2]| = |1 + (-3)| = 2. |A[1] + A[1]| = |4 + 4| = 8. |A[1] + A[2]| = |4 + (-3)| = 1. |A[2] + A[2]| = |(-3) + (-3)| = 6. 所以ans=1. 输入描述: 有多组测数数据,每组数据有两行,第一行包含一个正整数n(0<n<=100000),第二行包含n个整数,分别表示A[0],A[1],A[2],....,A[n-1],(|A[i]|<2^30)。 输入以文件结束。 输出描述: 对于每组数据,输出相应的答案。
解题思想:
- 首先将数组A进行排序(C语言可以使用qsort排序,效率很高),本人是采用非降序排序的。(其中i=0,j=n-1.)
- 然后分别从数组的头和尾进行对数组扫描,即前指针i和后指针j(这里的i、j时表示数组的下标)。在每次的A[i]和A[j]中都求其绝对值,即temp=|A[i]+A[j]|,然后和目前最小值min进行比较,即min=min<temp?min:temp;
- 接着,比较|A[i]|和|A[J]|的大小,如果A[i]>A[j],那么i++;否则j--;
- 最后求出来的就是所求结果。
本代码如下:
#include<stdio.h> #include<stdlib.h> #include<math.h> int arr[100000]; int cmp(const void *a,const void *b) { int *c=(int *)a; int *d=(int *)b; if(*c!=*d) return *c-*d; } int main() { int n,min,i,j,temp; while(scanf("%d",&n)!=EOF) { min=2100000000; for(i=0;i<n;i++) { scanf("%d",&arr[i]); } qsort(arr,n,sizeof(int),cmp); for(i=0,j=n-1;i<n && j>=0;) { temp=abs(arr[i]+arr[j]); if(temp<min) min=temp; if(abs(arr[i])>abs(arr[j])) { i++; } else { j--; } } printf("%d\n",min); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。