Trash Problem

Trash Problem

题意：

差分维护

有 \(n\) 堆垃圾，在不同的位置 \(p_i\)， 每次可以让一堆垃圾移动一格，垃圾可以合并，问最少移动多少次使得至多两堆垃圾

思路:

先将 \(p\) 排序，将 \([1,x]\) 合并成一堆 \([x+1,n]\) 合并成一堆

则花费为 \(p_n-p_1-(p_{x+1}-p_x)\) ，所以维护一个差分最大值就可以

用 \(set\) 和 \(multiset\) 进行维护

\(muiltiset\)

写了一个 \(map\) 版本的代码

写的好乱

#include<bits/stdc++.h>
using namespace std;

set<int>p;
map<int, int>d;

void add(int x) {
	if (p.empty()) {
		p.insert(x);
		return;
	}
	auto pos = p.lower_bound(x);

	if (pos == p.begin()) {
		d[*p.begin() - x]++;
	}
	else if (pos == p.end()) {
		d[x - *p.rbegin()]++;
	}
	else {
		int dx = *pos - *prev(pos);
		if (--d[dx] == 0)d.erase(dx);

		d[*pos - x]++;
		d[x - *prev(pos)]++;
	}

	p.insert(x);
}

void move(int x) {
	auto pos = p.find(x);
	//cout << *pos << endl;
	//cout << (pos == p.begin()) << endl;
	if (p.size() == 1) {
		p.erase(x);
		return; 
	}
	if (pos == p.begin()) {
	
		if (--d[*next(pos) - *pos] == 0)d.erase(*next(pos) - *pos);
	}
	else if (next(pos) == p.end()) {
		if (--d[*pos - *prev(pos)] == 0)d.erase(*pos - *prev(pos));
	}
	else {
		if (--d[*pos - *prev(pos)] == 0)d.erase(*pos - *prev(pos));
		if (--d[*next(pos) - *pos] == 0) d.erase(*next(pos) - *pos);
		d[*next(pos) - *prev(pos)]++;
	}
	//cout << "YES->move" << endl;
	p.erase(x);
}
int cal() {
	//cout << "YES->cal" << endl;
	if (p.size() <= 1)return 0;
	return *p.rbegin() - *p.begin() - (*d.rbegin()).first;
}

int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int val; cin >> val;
		p.insert(val);
	}
	for (auto i = next(p.begin()); i != p.end(); i++) {
		d[*i - *prev(i)]++;
	}
	cout << cal() << endl;

	for (int i = 1; i <= q; i++) {
		int op, x;
		cin >> op >> x;
		if (op == 1)add(x);
		else move(x);
		cout << cal() << endl;
	}
}

一份别人的代码。

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007LL
#define eps 1e-8
 
using namespace std;
 
set<int> a;
multiset<int> d;
 
void add(int x){
	set<int>::iterator it=a.lower_bound(x);
	if(it!=a.begin()&&it!=a.end())
		d.erase(d.lower_bound(*it-*prev(it)));
	if(it!=a.begin()) d.insert(x-*prev(it));
	if(it!=a.end()) d.insert(*it-x);
	a.insert(it,x);
}
 
void del(int x){
	set<int>::iterator it=a.lower_bound(x);
	it=a.erase(it);
	if(it!=a.begin()) d.erase(d.lower_bound(x-*prev(it)));
	if(it!=a.end()) d.erase(d.lower_bound(*it-x));
	if(it!=a.begin()&&it!=a.end()) d.insert(*it-*prev(it));
}
 
int calc(){
	if(a.size()<=2) return 0;
	return *a.rbegin()-*a.begin()-*d.rbegin();
}
 
int main()
{
	cin.tie(0),ios::sync_with_stdio(0);
	int n,q; cin>>n>>q;
	for(int i=0;i<n;i++){
		int x; cin>>x;
		add(x);
	}
	cout<<calc()<<"\n";
	while(q--){
		int op,x; cin>>op>>x;
		if(op==0) del(x);
		else add(x);
		cout<<calc()<<"\n";
	}
	return 0;
}

Trash Problem

原文：https://www.cnblogs.com/sduwh/p/13675883.html