MLE求优化思路
查看原帖
MLE求优化思路
759274
Stevehim楼主2023/2/11 19:09

RT

#include <bits/stdc++.h>
//2345浏览器
#define maxn 1000010
using namespace std;
typedef long long ll;

struct cow {
	int v, x;
} a[maxn];
int n;
vector<cow> p[maxn];

ll merge(int l, int r, int x) { //表示第x个奶牛在其连接的奶牛中的l到r的范围
	if (l == r) {
		return max(a[x].v, p[x][l - 1].v) * abs(a[x].x - p[x][l - 1].x);
	}
	int mid = (l + r) / 2; //有点线段树建树那味道了
	ll ans = 0;
	ans += merge(l, mid, x);
	ans += merge(mid + 1, r, x);
	return ans;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].v >> a[i].x;
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				continue;
			p[i].push_back(a[j]);
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += merge(1, n - 1, i);
	}
	cout << ans / 2;
	return 0;
}

2023/2/11 19:09
加载中...