[CCC2021 S3] Lunch Concert

题目描述

题目传送门

思路

题目可以表示为求：

$$\min\sum_{i=1}^nw_i \times\max(|c - p_i| - d_i,0)$$

发现对于每一个人，$c$ 移动时的贡献与 $w_i$ 相关。

后面的 $\max(|c - p_i| - d_i,0)$ 其实可以分成两种断点：

• $c-p_i$ 正负性断点;

• $\max$ 为 $0$ 断点。

那么动态维护断点答案取最小值就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
typedef long long ll;

int n;

struct _ {
	int type; //绝对值分界(1) / max为0(-1) 点
	int pos, id;
};
bool operator < (_ a, _ b) {
	return a.pos < b.pos;
}
struct __ {
	int p, w, d;
} a[MAXN];
vector<_> qwq;
void Add(int a, int b, int c) {
	qwq.push_back({b, a, c});
}

bool Max0[MAXN];
int Belong[MAXN];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int p, w, d;
		cin >> p >> w >> d;
		Add(p - d, 2, i);
		Add(p, 1, i);
		Add(p + d, 2, i);
		a[i] = {p, w, d};
	}
	stable_sort(qwq.begin(), qwq.end());
	ll c = qwq[0].pos - 1, res = 0, Ans = LLONG_MAX;
	ll Sumw = 0, _Sumw = 0;
	for (int i = 1; i <= n; i++) {
		res += max(abs(c - a[i].p) - a[i].d, 0ll) * a[i].w;
		if (c - a[i].p < 0) Sumw += a[i].w, Belong[i] = 1;
		else _Sumw += a[i].w, Belong[i] = -1;
	}
	Ans = min(Ans, res);
	for (int i = 0; i < qwq.size(); i++) {
		if (qwq[i].type == 1) {
			Belong[qwq[i].id] ^= 1;
		} else if (qwq[i].type == 2) {
			Max0[qwq[i].id] ^= 1;
			if (Max0[qwq[i].id]) {
				if (Belong[qwq[i].id] == 1) 
					Sumw -= a[qwq[i].id].w;
				else
					_Sumw -= a[qwq[i].id].w;
				if (i == 0) res -= a[qwq[i].id].w * (abs(qwq[i].pos - 1 - a[qwq[i].id].p) - a[qwq[i].id].d); 
				else res -= a[qwq[i].id].w * (abs(qwq[i - 1].pos - a[qwq[i].id].p) - a[qwq[i].id].d); 
			} else {
				if (i == 0) res = res + _Sumw - Sumw; 
				else res = res + (_Sumw - Sumw) * (qwq[i].pos - qwq[i - 1].pos);
				if (Belong[qwq[i].id] == 1) 
					Sumw += a[qwq[i].id].w;
				else
					_Sumw += a[qwq[i].id].w;
				goto End;
			}
		}
		if (i == 0) res = res + _Sumw - Sumw; 
		else res = res + (_Sumw - Sumw) * (qwq[i].pos - qwq[i - 1].pos);
		End:;
		Ans= min(Ans, res);
	}
	cout << Ans << endl;
	return 0;
}