CSP-S模拟14

T1.
考场：这不就单峰函数吗？我会
3min后：这函数有相等区间啊！爬山
3h后：woc这题写了3小时！赶紧去冲后几题暴力
不过最后还是A了

%:pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 3e5+10;
struct seg_s{
	int l, r;
}seg[N];
typedef unsigned long long ull;
mt19937 rd = mt19937(1919810);
typedef long long ll;
int rr(int l, int r){
	uniform_int_distribution <> d(l, r);
	return d(rd);
}
int calc(const seg_s& x, int y){
	if(y > x.r) return x.r;
	if(y < x.l) return x.l;
	else return y;
}
int n;
int tot;
ll a[N];
ll get_ans(int mid){
	ll ret = 0;
	ll rsum = 0;
	for(int i = 1; i <= n; ++i){
		a[i] = calc(seg[i], mid);
	}
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; ++i){
		rsum += a[i];
	}
	for(int i = 1; i <= n; ++i){
		rsum -= a[i];
		ret += rsum - a[i] * (n - i);
	}
	++tot;
	return ret;
}
ll get_dt(int mid){	
	ll ret = 0;
	ll rsum = 0;
	for(int i = 1; i <= n; ++i){
		a[i] = calc(seg[i], mid);
	}
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; ++i){
		rsum += a[i];
	}
	for(int i = 1; i <= n; ++i){
		rsum -= a[i];
		ret += a[i] - mid;
	}
	++tot;
	return ret;
}
ld S = 50, dt = 0.85, T = 0.001, Div = 1e4;
int mx = 0, mn;
int x;
ll Ans = 1e18;
void SimulateAnnel(){
	ld tem = S;
	while(tem > T){
		int dx = rr(floor(-tem / Div * mx), ceil(tem/Div * mx));
		// cerr<<"tem = "<<tem << "range = " << (ceil(tem/Div * mx) - floor(-tem / Div * mx)) << "x = " << x << endl;
		if(x + dx > mx || x + dx < 0) continue;
		ll nans = get_ans(x + dx);
		if(nans < Ans){
			x += dx, Ans = nans;
		}
		if(n > 1e4){
			if(tem > 1) {
				tem *= 0.7;
			}else if(tem < 0.01){
				tem *= 0.65;
			}else{
				tem *= 0.85;
			}
		}else{
			tem *= dt;
		}
	}
	for(int i = -2; i < 0; ++i){
		Ans = min(Ans, get_ans(x + i));
	}
	for(int i = 1; i <= 2; ++i){
		Ans = min(Ans, get_ans(x + i));
	}
}
int read(){
	int x = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	do{x = x * 10 + ch -'0', ch = getchar();}while(isdigit(ch));
	return x;
}
int main(){
	// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	// cin >> n;
	n = read();
	if(n <= 1e4){
		S = 1E4, dt = 0.92, T = 0.01;
	}
	for(int i = 1; i <= n; ++i){
		// cin >> seg[i].l >> seg[i].r;
		seg[i].l = read(), seg[i].r = read();
		mx = max(mx, seg[i].r);
		mn = min(mn, seg[i].l);
	}
	int l = mn, r = mx, res = (mx + mn) / 2;
	while(r - l > 3e3){
		int mid = (l + r) >> 1;
		if(get_dt(mid) <= 0){
			res = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}
	x = res;
	// x = (mx + mn)/ 2;
	int cnt = 1;
	SimulateAnnel();	
	// cerr<<"rawx " << res << endl;
	// cerr<<"x = " << x << endl;
	// cerr<<"tot = " << tot << endl;
	// cerr<<"dtx = " << x - res << "val = "<<1.0 * (x - res)/mx << endl;
	// printf("%lld", ans);
	cout << Ans << endl;
	// cout << fixed<< setprecision(0) << round(Ans) << endl;
	return 0;
}