题解:
这个题他要求数组内相加差值最小的数,我的思路是排序+双指针。
但是这个双指针的内部操作有几点是要注意的。
1.排序:如何排序?
我们先按照元素大小进行排序,再按照其下表进行排序,为什么第二点要按照下标进行排序,后面我会说一下。
2.双指针:
首先我们用l指针指向排好序的第一个元素,再用r指针指向排好序的最后一个元素。
之后我们不断的从两边往中间夹。
(1)首先我们把元素相加的绝对值给算出来,看看他是不是目前最小的,如果不是就更新当前最小及其下标之和,如果跟当前最小值相等的话,那么就检查一下看看是否可以更新下表之和的最小值。
(2)如何判断该移动哪个指针呢。
如果两者之和小于0那么我们就把左指针往右移动
如果两者之和大于0那么我们就把右指针往左移动
下面我们看一个样例:
5 -1 -1 0 1 1
这个样例该如何移动?
我们前面排序的方法是如果元素值相同就按照其下表进行排序
所以如果相加等于0,那么我们只需要把右指针往左移动即可,因为只有把右指针往左移动,才能减少其下表最小值
重点:
那么我们再看题目给的样例
5 -2 6 7 7 -8
我们发现排好序后是,下面的数代表他的初始下表
-8 -2 6 7 7 5 1 2 3 4
很明显-8跟到数第二个7组合会得到最优解。
既然这样的话,我们就根本不需要特判左端点元素值+右端点元素值相等的时候在移动右端点,有可能元素和最优解并不是的0,所以在判断如何移动的时候,我们先进行判断右端点是否跟右端点-1的值相同,如果相同就移动右端点,因为越靠左边下标越小
/*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int mod = 100000000; using namespace std; struct wazxy{ int val,pos; }a[maxn]; struct rule{ bool operator()(const wazxy & a,const wazxy & b){ if(a.val!=b.val) return a.val<b.val; else return a.pos<b.pos; } }; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i].val); a[i].pos=i; } sort(a+1,a+n+1,rule()); int l=1,r=n; int imin=MaxN,ans; while(l<r){ //cout<<"L:"<<l<<" "<<r<<endl; int sum=abs(a[l].val+a[r].val); if(sum<imin) imin=sum,ans=a[l].pos+a[r].pos; else if(sum==imin) ans=min(ans,a[l].pos+a[r].pos); if(a[r].val==a[r-1].val) r--; else if(a[l].val+a[r].val>=0) r--; else if(a[l].val+a[r].val<0) l++; } cout<<imin<<" "<<ans<<endl; return 0; }