放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

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//////////////////////////////////
13233480 hankcs 1201 Accepted 996K 204MS C++ 1870B 2014-08-03 00:30:54

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

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    你好~这样解的话复杂度似乎是O(N^2)吧?因为每次查找没有用过的数字都是从后往前一个个找,如果我的数据是这样:(25000,25000,1)(24999,25001,3) (24998,25002,5)…(0,50000,50001),这样的话,复杂度就会达到N^2了。这是我的一点愚见,不知是否正确,还望指教

    小立子6年前 (2018-08-04)回复
    • 其实我认为可以这样:
      如果当前区间[l, r]已选择的数量小于ci,则可以把[r-ci+1, r]的值都改成1,这样就避免了一个一个去找的时间冗余

      115年前 (2019-04-03)回复
    • 其实我认为可以这样:
      如果当前区间[l, r]已选择的数量小于ci,则可以把[r-ci+1, r]的值都改成1,这样就避免了一个一个去找的时间冗余

      11111115年前 (2019-04-03)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》