Professor GukiZ and Two Arrays
题解:
将a数组都sort一遍之后, b数组也sort一遍之后。
可以观察得到 对于每一个ai来说, 整个数组bi是一个V型的。
并且对于ai+1的最优解一定是在ai的右边。
然后我们将a数组 和 b数组枚举一遍。
然后再将a数组22组合, b数组22组合之后, 再枚举一遍。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 4e6 + ;
int a[N], b[N];
struct Node{
int v, l, r;
bool operator<(const Node & t) const{
return v < t.v;
}
}A[N], B[N];
LL ans;
pll ansa, ansb;
LL suma = , sumb = ;
int f;
LL cal(int i, int j){
LL tsuma = suma - A[i].v + B[j].v;
LL tsumb = sumb - B[j].v + A[i].v;
return abs(tsuma - tsumb);
}
void Find(int n, int m){
if(!n || !m) return ;
sort(A+, A++n); sort(B+, B++m);
for(int i = , j = ; i <= n; ++i){
while((j+) <= m && cal(i,j) >= cal(i,j+)) ++j;
if(ans > cal(i,j)){
ans = cal(i, j);
ansa = pll(A[i].l, B[j].l);
ansb = pll(A[i].r, B[j].r);
}
}
}
int main(){
int n, m;
scanf("%d", &n);
f += (n==);
for(int i = ; i <= n; ++i){
scanf("%d", &a[i]);
A[i] = {a[i], i, };
suma += a[i];
}
scanf("%d", &m);
for(int i = ; i <= m; ++i){
scanf("%d", &b[i]);
B[i] = {b[i], i, };
sumb += b[i];
}
ans = abs(suma - sumb); ansa = ansb = {, };
Find(n, m);
int atot = , btot = ;
for(int i = ; i <= n; ++i){
for(int j = i+; j <= n; ++j){
A[++atot] = {a[i]+a[j], i, j};
}
}
for(int i = ; i <= m; ++i){
for(int j = i+; j <= m; ++j){
B[++btot] = {b[i]+b[j], i, j};
}
}
Find(atot, btot);
printf("%lld\n", ans);
if(ansa.fi == ){
puts("");
}
else if(ansb.se == ){
puts("");
printf("%d %d\n", ansa.fi, ansa.se);
}
else {
puts("");
printf("%d %d\n", ansa.fi, ansa.se);
printf("%d %d\n", ansb.fi, ansb.se);
}
return ;
}