程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #251 (Div. 2) D 二分

Codeforces Round #251 (Div. 2) D 二分

編輯：C++入門知識

Codeforces Round #251 (Div. 2) D 二分

是個不錯的題目，首先多畫幾個不難發現，若要滿足題目條件有可能 a數組的最小值要不斷增大，也有可能b數組的最大值不斷減小，一開始直接用了優先隊列，發現了不對的地方，因為沒一次有兩個情況要麼a加要麼b減，所以不能直接來，多畫幾個不難發現，我們需要找到一個值 x是的 a中所有元素都大於等於x，而b中所有元素都小於等於x,所以只需要找到這個x即可，根據多畫了幾個的情況發現x應該是在a跟b中的元素之一，所以多畫了幾個發現都正確，那麼直接在a,b數組中暴力查找，然後再進行二分查找答案，然後獲得最終最小的那個答案，求答案需要維護一下 a的前綴和與b的後綴和即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

const int inf = 0xfffffff;

const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;


int n,m;

ll ans;

ll aa[100000 + 55],bb[100000 + 55];

ll sa[100000 + 55],sb[100000 + 55];

vector G;

void init() {
	memset(aa,0,sizeof(aa));
	memset(bb,0,sizeof(bb));
	memset(sa,0,sizeof(sa));
	memset(sb,0,sizeof(sb));
	G.clear();
}

bool input() {
	while(scanf(%d %d,&n,&m) == 2) {
		for(int i=1;i<=n;i++) {scanf(%I64d,&aa[i]);G.push_back(aa[i]);}
		for(int i=1;i<=m;i++) {scanf(%I64d,&bb[i]);G.push_back(bb[i]);}
		return false;
	}
	return true;
}

ll find(ll x) {
	ll sum = 0;
	int pos = lower_bound(aa + 1,aa + n + 1,x) - aa;
	sum += (pos - 1) * x - sa[pos - 1];
	pos = lower_bound(bb + 1,bb + m + 1,x) - bb;
	sum += sb[pos] - (m - pos + 1) * x;
	return sum;
}

void cal() {
	sort(aa + 1,aa + n + 1);
	sort(bb + 1,bb + m + 1);
	sort(G.begin(),G.end());
	for(int i=1;i<=n;i++)sa[i] = sa[i - 1] + aa[i];
	for(int i=m;i>0;i--)sb[i] = sb[i + 1] + bb[i];
	ans = INF;
	for(int i=0;i