L3-017 森森快递(天梯赛)

https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805047638999040

大意是在一条直线上,有N个从0..N-1编号的城市,每个城市之间的道路有最大负载ai,现在有M张从i城到j城的运货订单,假设每个城市的货物无限,问在某一时刻,如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？

分析：开始想到的是按照区间长度依次操作 因为小区间对别的区间的影响可能性要小一些 但是这样做是错误的 就算影响小一些 但是仍然可能有

正确的做法是 按照第一关键字右端点从小到大 第二关键字左端点从大到小排序

为什么？

首先,这是一个区间调度问题,性质如同问:有许多项工作,每个工作有起始结束时间,目标是尽可能多的选择工作,问最多可参与几项工作? 工作结束得越早,那么之后可选择的工作自然越多. 这道题是一样的,货物的终点站越靠左,那么留出了越多道路给后面的订单. 这里是贪心的思想.

然后就线段树区间修改区间最小值即可

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
typedef struct node{
	int l, r;
	ll minn, f;
	bool operator < (const node x) const {
		if(x.r != r)	
			return x.r > r;
		else
			return x.l < l;
	}	
}node; 
node tree[maxn<<2];
node ans[maxn];
ll minn;

void down(int k){
	if(tree[k].f){
		tree[k<<1].f += tree[k].f;
		tree[k<<1|1].f += tree[k].f;
		tree[k<<1].minn -= tree[k].f;
		tree[k<<1|1].minn -= tree[k].f;
		tree[k].f = 0; 
	}	
}

void build(int k, int l, int r){
	tree[k].l = l, tree[k].r = r;
	if(l == r){
		scanf("%lld", &tree[k].minn);
		return;
	}
	int mid = (l+r)>>1;
	build(k<<1, l, mid);
	build(k<<1|1, mid+1, r);
	tree[k].minn = min(tree[k<<1].minn, tree[k<<1|1].minn);
}

void query(int k, int l, int r, int cl, int cr){
	if(l >= cl && r <= cr){
		minn = min(minn, tree[k].minn);
		return;
	}	
	down(k);
	int mid = (l+r)>>1;
	if(cl <= mid)	query(k<<1, l, mid, cl, cr);
	if(cr > mid)	query(k<<1|1, mid+1, r, cl ,cr);
}

void swap(int &x, int &y){
	int t = x; x = y; y = t;
}

void updata(int k, int l, int r, int cl, int cr, ll c){
	if(l >= cl && r <= cr){
		tree[k].f += c;
		tree[k].minn -= c;
		return;
	}	
	down(k);
	int mid = (l+r)>>1;
	if(cl <= mid)	updata(k<<1, l, mid, cl, cr, c);
	if(cr > mid)	updata(k<<1|1, mid+1, r, cl, cr, c);
	tree[k].minn = min(tree[k<<1].minn, tree[k<<1|1].minn);
} 

int n, q;
int main(){
	int a, b;
	scanf("%d %d", &n, &q);
	build(1, 1, n-1);
	for(int i = 0; i < q; ++ i){
		scanf("%d %d", &a, &b);
		if(a > b)	swap(a, b);
		ans[i].l = a+1;
		ans[i].r = b;	
	}
	sort(ans, ans+q);
	ll sum = 0;
	for(int i = 0; i < q; ++ i){
		minn = 1e18;
		query(1, 1, n-1, ans[i].l, ans[i].r);
		sum += minn;
		updata(1, 1, n-1, ans[i].l, ans[i].r, minn);
	}
	printf("%lld\n", sum);
	return 0;
}