思路一:
3个数组都按照小到大排序,设置3个指针,起始都在数组的末尾,如果1个指针向前移动1位可以让对应元素和另两个数组元素的距离之和减小,则移动它。如果某一回合三个指针都没动,就跳出循环。
非满分:23/25,应该是数据比较弱。
思路一代码:
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>using namespace std;const int maxn = 10010;int A[maxn],B[maxn],C[maxn];int main(){ int la,lb,lc;cin>>la>>lb>>lc;for(int i=0;i<la;i++){cin>>A[i];}sort(A,A+la);for(int i=0;i<lb;i++){cin>>B[i];}sort(B,B+lb);for(int i=0;i<lc;i++){cin>>C[i];}sort(C,C+lc);int ia = la-1,ib = lb-1,ic = lc-1;while(ia>0||ib>0||ic>0){bool changed = false;if(abs(A[ia-1]-B[ib])+abs(A[ia-1]-C[ic])<abs(A[ia]-B[ib])+abs(A[ia]-C[ic])&&ia>0){ia--;changed = true;}if(abs(A[ia]-B[ib-1])+abs(B[ib-1]-C[ic])<abs(A[ia]-B[ib])+abs(B[ib]-C[ic])&&ib>0){ib--;changed = true; }if(abs(A[ia]-C[ic-1])+abs(B[ib]-C[ic-1])<abs(A[ia]-C[ic])+abs(B[ib]-C[ic])&&ic>0){ic--;changed = true;}if(changed == false)break;}int minD = abs(A[ia]-B[ib])+abs(A[ia]-C[ic])+abs(B[ib]-C[ic]);printf("MinD(%d, %d, %d) = %d",A[ia],B[ib],C[ic],minD);return 0;
}