首页 > 代码库 > Codeforces 439D Devu and his Brother 三分

Codeforces 439D Devu and his Brother 三分

题目链接:点击打开链接

= - =以前的三分姿势不正确居然没有被卡掉,,,太逗。。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define M 200004
#define N 100040
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define ll __int64
#define Sum(x) tree[x].sum
#define Mod(x) tree[x].mod
#define inf 1000000000
ll n,m;
ll a[N],b[N];
ll ok(ll x){
	ll ans = 0;
	for(ll i = 1; i <= n; i++)if(x>a[i])ans+=(x-a[i]);
	for(ll i = 1; i <= m; i++)if(x<b[i])ans+=(b[i]-x);
	return ans;
}
int main(){
	ll i,j,u,v;
	while(~scanf("%I64d %I64d",&n,&m)){
		ll minn = inf, maxx = 0;
		for(i=1;i<=n;i++)scanf("%I64d",&a[i]), minn = min(minn,a[i]);
		for(i=1;i<=m;i++)scanf("%I64d",&b[i]), maxx = max(maxx,b[i]);
		if(minn>=maxx){puts("0");continue;}
		ll ans = inf;
		ll l = minn, r = maxx;
		ans = min(ok(l),ok(r));
		while(l<r){
			ll mid1 = (l+r)/2, mid2 = (mid1+r)/2;
			ll tmp1 = ok(mid1), tmp2 = ok(mid2);
			if(tmp1>tmp2)
				l = mid1;
			else r = mid2;
			ans = min(ans, min(tmp1, tmp2));
		}
		printf("%I64d\n",ans);
	}
	return 0;
}
/*
2 2
2 3
3 5
3 2
1 2 3
3 4
3 2
4 5 6
1 2

*/