首页 > 代码库 > A题之绝对值最小问题
A题之绝对值最小问题
时间:2014.05.08
地点:基地
--------------------------------------------------------------------------
一、题目详情
给你一个数组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)。
输入以文件结束。
输出描述:
对于每组数据,输出相应的答案。
-----------------------------------------------------------
二、答题说明
输入样例:
3
1 4 -3
1
2
3
-1 -2 -5
3
1 2 3
2
0 5
输出样例:
1
4
2
2
0
-----------------------------------------------------------
三、我的情况说明
我是想着明明是应该是没问题了啊,但就是没有AC过,不知道原因出在哪里,于是怕可能是输入输出不合要求研究了一番输入输出,还是不过,好吧,先这样着了,如果有大神看出名堂来了希望告之一下,至少我自己测试过的很多组数据是没有任何问题的。
-----------------------------------------------------------
四、思路
我的思路就是借助快速排序的思想,先将数组排序,但这里的排序和快排有点点区别,我是按他们的绝对值大小进行快排,时间复杂度为O(nlogn),然后再挑出和最小的绝对值,这里时间复杂度为O(n),所以总的时间复杂度就是O(nlogn)。
我们来看:经过按绝对值排序后,这些绝对值最小可能来自于来两种情况
1.就是首元素的两倍,因为后面元素自身的两倍绝对值肯定要比首元素自身的两倍要大或等于了
2.来自数组中不同两个元素的和的绝对值,首先,这两个元素中必然有一个是负数,两个都是正数的和肯定也要比首元素的和的绝对值要大,于是,我们对数组进行一次遍历,每遇到一个负数,我们都去看它与前面后面的值的和是什么情况
3.上述两种情况得出的最小值取出最小值,即所求的最小值。
-----------------------------------------------------------
五、实现代码如下,自己测试一直通过,提交代码却一直不通过,忘大神指点迷津
#include<iostream> using namespace std; int abs(int data) { return (data >= 0) ? data : -data; } int Partion(int in_array[], int lo, int hi) { int left = lo, right = hi, base_element = in_array[lo]; while (left<right) { while ((right>left) && (abs(in_array[right]) > abs(base_element))) --right; if (right > left) { in_array[left] = in_array[right]; ++left; } while ((left <right) && (abs(in_array[left]) < abs(base_element))) ++left; if (left < right) { in_array[right] = in_array[left]; --right; } } in_array[right] = base_element; return left; } void QuickSort(int in_array[], int lo, int hi) { if (lo >= hi) return; int j = Partion(in_array, lo, hi); QuickSort(in_array, lo, j - 1); QuickSort(in_array, j + 1, hi); } int MinAbsoluteSum(int arr[], size_t size) { QuickSort(arr, 0, size); int min_absolute_sum = 2*abs(arr[0]); int possible_min_left = abs(arr[0] + arr[1]); int possible_min_right = abs(arr[size-1] + arr[size-2]); int possible_min = 0; for (size_t i = 1; i < size-1; ++i) { if (arr[i] < 0) { int temp_min_left = abs(arr[i] + arr[i - 1]); int temp_min_rigth = abs(arr[i] + arr[i + 1]); possible_min_left = (possible_min_left < temp_min_left) ? possible_min_left : temp_min_left; possible_min_right = (possible_min_right < temp_min_rigth) ? possible_min_right : temp_min_rigth; } } possible_min = (possible_min_left < possible_min_right) ? possible_min_left : possible_min_right; return (min_absolute_sum < possible_min) ? min_absolute_sum : possible_min; } int main() { size_t n; while (cin >> n) { int* p_arr = new int[100000]; size_t count = 0; while (count<n) { cin>>p_arr[count]; ++count; } int min = MinAbsoluteSum(p_arr, n); cout << min << endl; delete[] p_arr; } return 0; }