首页 > 代码库 > 分篮子

分篮子

题意:

一共有n(<=1e5)个元素,每一个元素都有三个关键字,a,b,c现在将这些元素分给A,B,C,这些元素价值在A手中的体现为,所有元素中最大的a值,在B中则是最大b值,C也是一样的,现在要有一种分法,求A+B+C的最小值。

 

题解:

首先想到的是n^2的算法,首先将所有元素按照a关键字从小到大,然后在开一个数组按照b关键字排序,然后从小到大枚举a,然后标记,然后从大到小枚举b,记录c的最大值,就可以一直更新答案。

既然知道了n^2的算法,现在想是否可以优化呢?枚举a是必然的,如果从小到大枚举a,无异是在b中删除元素,那么从大到小枚举a的话,就是在b中增加元素,删除是不好处理的,那么现在从大到小枚举a,那么现在的问题是在b中优化了。

b是从小到大排了序的,那么如果要选第i个,那么就需要知道(i + 1) ~ n中c的最大值,那么现在就会发现一个单调性便是在b中,随着b的增大,c的最大值一定是不上升的。

现在考虑新增加一个元素,那么这个元素会对它前面的比他的c小的b的c的最大值造成影响,那么现在就需要知道第一个小于等于这个元素的c值的位置,然后一并更新。

怎么知道那个位置呢?二分啊QAQ。怎么区间更新呢?线段树啊QAQ。

然后现在考虑求得答案,答案的组成是A+B+C,A是通过枚举的,现在的问题是求B+C的最小值,线段树也可以一并维护B+C了,线段树也要维护一个C的最大值。

 

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 7;
int disc[N], dcnt, n, ans = 1e9 + 7;
int mi[N << 2], vc[N << 2], lz[N << 2];
struct node {int a, b, c;} ai[N];

#define mid (l + r >> 1)
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r

bool cmp (node a, node b) {return a.a < b.a;}

void pushdown (int o, int l, int r)
{
	if (!lz[o]) return;
	mi[o << 1] = disc[l] + lz[o], vc[o << 1] = lz[o], lz[o << 1] = lz[o];
	mi[o << 1 | 1] = disc[mid + 1] + lz[o], vc[o << 1 | 1] = lz[o], lz[o << 1 | 1] = lz[o];
	lz[o] = 0;
}

void update (int o, int l, int r, int L, int R, int x)
{
	if (l == L && r == R)
	{
		mi[o] = disc[L] + x;
		vc[o] = x;
		lz[o] = x;
		return;
	}
	pushdown(o, l, r);
	if (R <= mid) update (lson, L, R, x);
	else if (L > mid) update (rson, L, R, x);
	else update (lson, L, mid, x), update (rson, mid + 1, R, x);
	mi[o] = min (mi[o << 1], mi[o << 1 | 1]);
}

int query (int o, int l, int r, int x)
{
	if (l == r) return vc[o];
	pushdown(o, l, r);
	if (x <= mid) return query (lson, x);
	else if (x > mid) return query (rson, x);
}

int getpos (int l , int r, int d)
{
	while (l < r)
	{
		if (query(1, 1, dcnt, mid) < d) r = mid;
		else l = mid + 1;
	}
	return l;
}

void build (int o, int l, int r)
{
	if (l == r) 
	{
		mi[o] = disc[l];
		return;
	}
	build (lson);
	build (rson);
	mi[o] = min (mi[o << 1], mi[o << 1 | 1]);
}

int main ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++ i)
	{
		scanf ("%d%d%d", &ai[i].a, &ai[i].b, &ai[i].c);
		disc[++dcnt] = ai[i].b;
	}
	disc[++dcnt] = 0;
	sort (ai + 1, ai + 1 + n, cmp);
	sort (disc + 1, disc + 1 + dcnt);
	dcnt = unique (disc + 1, disc + 1 + dcnt) - disc - 1;
	build (1, 1, dcnt);
	ans = ai[n].a;
	for (int i = n; i >= 1; -- i)
	{
		int p = lower_bound (disc + 1, disc + 1 + dcnt, ai[i].b) - disc;
		int pos = getpos(1, p, ai[i].c);
		if (pos <= p - 1) update (1, 1, dcnt, pos, p - 1, ai[i].c);
		ans = min (ans, ai[i - 1].a + mi[1]);
	}
	cout << ans << endl;
	return 0;
}

  

总结:

首先需要想到暴力,然后再优化就理所当然了,还有的就是要发现序列的单调性。

 

分篮子