一种很新的二分答案写法

日期:
标签: oi trick

原理

众所周知,C++ 中的 algorithm 中有 std::upper_boundstd::lower_bound 函数用于二分查找。

简单来说,这两个函数前两个参数是两个迭代器以指定二分的范围,第三个参数是需要二分的值,第四个参数是比较函数。

然而这种二分通常来说无法二分答案,因为当答案范围很大的时候,你无法生成值域大小的数组。然而我们可以把 int 封装成一个迭代器,把它传到 stl 中。这个迭代器不需要实际地指向某个元素,因此不会占用内存。

代码如下:

struct int_iterator
{
public:
	using value_type = const long long;
	using difference_type = long long;	
	using pointer = const long long *;
	using reference = const long long;
	using iterator_category = std::random_access_iterator_tag;
	
	int_iterator() : _val(0) {}
	int_iterator(long long x) : _val(x) {}
	
	value_type operator*() const { return _val; }
	
	int_iterator &operator+=(difference_type n)
	{
		_val += n;
		return *this;
	}
	
	int_iterator &operator++() { return *this += 1; }
	
	int_iterator &operator--() { return *this += -1; }
	
	difference_type operator-(const int_iterator &iit) const
	{
		return _val - iit._val;
	}

private:
	long long _val;
};

首先,前几行 using 是迭代器的必需定义,只有定义了这些量,标准库才能用 std::iterator_traits 访问迭代器的各个属性。iterator_category 被定义成了 std::random_access_iterator_tag,即 老式随机访问迭代器。这样调用 STL 时,STL 会用 += 来实现 std::advance,而不是一个一个地自增,也会用 - 来求两个迭代器的距离,保证复杂度正确(这也是为什么不要在 map、set 上直接用 STL 二分而用自带二分的原因)。

RandomAccessIterator 要求定义的运算符很多,然而我们可以根据 std::upper_boundstd::lower_bound 调用的运算符按需定义。

例子

P1873:给定一个长度为 的数组 ,和一个正整数 ,求最大的 使得

int main()
{
	int n;
	long long m;
	scanf("%d%lld", &n, &m);
	std::vector<int> a(n);
	for (auto &i : a) scanf("%d", &i);

	auto cmp = [&a](const int &mid, const long long &m)
	{
		long long sum = 0;
		for (auto i : a) sum += std::max(0, i - mid);
		return sum >= m;
	};

	int ans = std::lower_bound(int_iterator(0), 
				   int_iterator(*std::max_element(a.begin(), a.end())), 
				   m, 
				   cmp) - int_iterator(0) - 1;

	printf("%d\n", ans);
}