POJ 1201 Intervals 题解 《挑战程序设计竞赛》

POJ 1201 Intervals

乞巧：从一系列区间[a_i,b_i]中至少取出c_i个数构成集合s，求s的最小size？

3.3活用各种数据结构

线段树和平方分割

呵呵，白天睡了一天，晚上吃完翔后怎么也睡不着，爬起来再A一题吧。

这题基本思路是贪心，从尾部最小的区间开始，尽量挑尾部的数，这样可能与后面的区间发生共用关系，从而降低集合的大小。但是在查询这个集合的区间内部已经有多少个点被选走的时候，朴素算法太慢了，这时候可以用BIT或线段树来维护。

把前面写的BIT模板拖过来改改就过了。

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

#define MAX_N 50000 + 16

typedef struct Range
{
	int a;
	int b;
	int c;
	bool operator < (const Range& other) const
	{
		return b < other.b;
	}
};

Range range[MAX_N];
bool used[MAX_N];


template <class T>
class BinaryIndexedTree
{
public:
	T bit[MAX_N];
	int size;

	BinaryIndexedTree(){}

	void init(int size)
	{
		this->size = size;
		memset(bit, 0, sizeof(bit));
	}

	T sum(int i)
	{
		++i;
		int s = 0;
		while (i > 0)
		{
			s += bit[i];
			i -= (i & -i);
		}
		return s;
	}

	// 求和a[from, to)
	T sum(int from, int to)
	{
		return sum(to - 1) - sum(from - 1);
	}

	void add(int i, T v)
	{
		++i;    // 防止如果i是0的话，下面的循环永远不会终止
		while (i <= size)
		{
			bit[i] += v;
			i += (i & -i);
		}
	}
};

BinaryIndexedTree<int> bit; 

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	
	scanf("%d", &n);
	bit.init(MAX_N);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d%d", &range[i].a, &range[i].b, &range[i].c);
	}

	sort(range, range + n);
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		int picked = bit.sum(range[i].a, range[i].b + 1);
		if (picked < range[i].c)
		{
			int remain = range[i].c - picked;
			result += remain;
			int tail = range[i].b;
			while (remain)
			{
				if (used[tail] == false)
				{
					used[tail] = true;
					bit.add(tail, 1);
					--remain;
				}
				--tail;
			}
		}
	}
	printf("%d\n", result);

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1201 Intervals 题解 《挑战程序设计竞赛》