Min Value

题目：Min Value
来源：哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）

解题思路

给定一个由 个数组成的序列 ，从中任选两个数 和 ，使得 的绝对值最小，并且计算出 的值，其中 。

使用双指针。

先将序列中的数从小到大排序。如果两个数相等，下标小的排前面。a[i][0] 表示第 i 小的数值，a[i][1] 是其对应的原下标。
将 i 和 j 分别指向排序后序列的首元素和尾元素。

1. 如果 a[j-1][0] == a[j][0]，数值相等，但 a[j-1][1] < a[j][1]，将 j 左移。
2. i 和 j 指向的数值均大于等于 0，那么不管是 i 还是 j 向右移，两数相加的绝对值均比现在要大，所以将 j 左移。
3. i 和 j 指向的数值均小于等于 0，那么不管是 i 还是 j 向左移，两数相加的绝对值均比现在要大，所以将 i 右移。
4. i 指向的值小于 0，j 指向的值大于 0，哪边的绝对值大，移动哪边。
   比如，i 指向 x <= 0，j 指向 y >= 0，则两者相加的绝对值为 abs(-x - y)，如果 -x > y，小于 y 的值与 x 相加得到的绝对值一定大于当前的绝对值，将 j 左移没有必要，所以将 i 右移；否则将 j 左移。

C++代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

bool comp(vector<int>& v1, vector<int>&v2){
    if(v1[0] < v2[0])
        return true;
    else if(v1[0] == v2[0])
        return v1[1] < v2[1];
    return false;
}

int main(){
    int N;
    scanf("%d", &N);
    vector<vector<int>> a(N, vector<int>(2));
    for(int i=0; i<N; ++i){
        scanf("%d", &a[i][0]);
        a[i][1] = i+1;
    }
    sort(a.begin(), a.end(), comp);
    long long minVal = 1e12+1;
    int minIndex = 2e5;
    int i = 0;
    int j = N-1;
    while(i < j){
        long long sum = abs(1LL * a[i][0] + a[j][0]);
        if(sum < minVal){
            minVal = sum;
            minIndex = a[i][1] + a[j][1];
        }
        else if(sum == minVal){
            minIndex = min(minIndex, a[i][1] + a[j][1]);
        }
        if(a[j][0] == a[j-1][0])
            --j;
        else if(a[i][0] >= 0)
            --j;
        else if(a[j][0] <= 0)
            ++i;
        else{
            if(-a[i][0] > a[j][0])
                ++i;
            else
                --j;
        }
    }
    printf("%lld %d\n", minVal, minIndex);
    return 0;
}