傳送門
文章目錄
題意：
給你三個數(shù)組a,b,ca,b,ca,b,c，讓你從每個數(shù)組中選擇一個數(shù)x,y,zx,y,zx,y,z，使得(x?y)2+(x?z)2+(y?z)2(x-y)^2+(x-z)^2+(y-z)^2(x?y)2+(x?z)2+(y?z)2最小，求這個最小值。
思路：
由于答案一定是x≤y≤zx\le y\le zx≤y≤z的形式(當(dāng)然這里的x,y,zx,y,zx,y,z與題意的x,y,zx,y,zx,y,z不同)，所以我們就可以跑一個3!3!3!排列，讓他們分別為x,y,zx,y,zx,y,z，讓后枚舉其中一個二分另外倆就行了。
具體實現(xiàn)可以寫個函數(shù)就比較方便了。
我這里寫的是枚舉xxx，讓后分兩種即找yyy和找zzz，如果找yyy的話，假設(shè)現(xiàn)在已經(jīng)有x≤yx\le yx≤y了，那么找的zzz根據(jù)平方的性質(zhì)，最好是x+(y?x)/2x+(y-x)/2x+(y?x)/2附近的位置，二分找即可，對于zzz同理。
總結(jié)：這個題瞎搞都能過。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const LL inf
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-6;int n1
,n2
,n3
;
LL a
[N
],b
[N
],c
[N
];LL
get(int i
,int j
,int k
) {return (a
[i
]-b
[j
])*(a
[i
]-b
[j
])+(a
[i
]-c
[k
])*(a
[i
]-c
[k
])+(b
[j
]-c
[k
])*(b
[j
]-c
[k
]);
}LL
solve() {LL ans
=inf
;for(int i
=1;i
<=n1
;i
++) {int val1
=a
[i
];int pos1
=lower_bound(b
+1,b
+1+n2
,val1
)-b
;if(pos1
<=n2
) {int pos2
=lower_bound(c
+1,c
+1+n3
,a
[i
]+(b
[pos1
]-a
[i
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
++;if(pos1
<=n2
) {int pos2
=lower_bound(c
+1,c
+1+n3
,a
[i
]+(b
[pos1
]-a
[i
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
-=2;if(pos1
>=1) {int pos2
=lower_bound(c
+1,c
+1+n3
,b
[pos1
]+(a
[i
]-b
[pos1
])/2)-c
;if(pos2
<=n3
) ans
=min(ans
,get(i
,pos1
,pos2
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos1
,pos2
));}pos1
=lower_bound(c
+1,c
+1+n3
,val1
)-c
;if(pos1
<=n3
) {int pos2
=lower_bound(b
+1,b
+1+n2
,a
[i
]+(c
[pos1
]-a
[i
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}pos1
++;if(pos1
<=n3
) {int pos2
=lower_bound(b
+1,b
+1+n2
,a
[i
]+(c
[pos1
]-a
[i
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}pos1
-=2;if(pos1
>=1) {int pos2
=lower_bound(b
+1,b
+1+n2
,c
[pos1
]+(a
[i
]-c
[pos1
])/2)-b
;if(pos2
<=n2
) ans
=min(ans
,get(i
,pos2
,pos1
)); pos2
--;if(pos2
>=1) ans
=min(ans
,get(i
,pos2
,pos1
));}}return ans
;
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d%d",&n1
,&n2
,&n3
);for(int i
=1;i
<=n1
;i
++) scanf("%lld",&a
[i
]);for(int i
=1;i
<=n2
;i
++) scanf("%lld",&b
[i
]);for(int i
=1;i
<=n3
;i
++) scanf("%lld",&c
[i
]);sort(a
+1,a
+1+n1
); sort(b
+1,b
+1+n2
); sort(c
+1,c
+1+n3
);n1
=unique(a
+1,a
+1+n1
)-a
-1;n2
=unique(b
+1,b
+1+n2
)-b
-1;n3
=unique(c
+1,c
+1+n3
)-c
-1;printf("%lld\n",solve());}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #635 (Div. 2) D. Xenia and Colorful Gems 暴力 + 二分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
