Tag Archives: 分治法

LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。
第一敏感使用线段树,很久之前在hihoCoder上遇到过
建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。
查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。
更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。
完整代码如下:

class NumArray {
private:
	struct Node {
		int start, end, sum;
		Node *left, *right;
		Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
	};
	Node *root;
	Node* constructTree(vector<int> &nums, int start, int end) {
		Node* node = new Node(start, end);
		if (start == end) {
			node->sum = nums[start];
			return node;
		}
		int mid = start + (end - start) / 2;
		node->left = constructTree(nums, start, mid);
		node->right = constructTree(nums, mid + 1, end);
		node->sum = node->left->sum + node->right->sum;
		return node;
	}
	int sumRange(int i, int j, Node *root) {
		if (root == NULL)return 0;
		if (i == root->start&&j == root->end)return root->sum;
		int mid = root->start + (root->end - root->start) / 2;
		if (j <= mid)return sumRange(i, j, root->left);
		else if (i > mid)return sumRange(i, j, root->right);
		else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
	}
	void update(int i, int val, Node *root) {
		if (root->start == root->end && root->start == i) {
			root->sum = val;
			return;
		}
		int mid = root->start + (root->end - root->start) / 2;
		if (i <= mid)update(i, val, root->left);
		else update(i, val, root->right);
		root->sum = root->left->sum + root->right->sum;
	}
public:
	NumArray(vector<int> nums) {
		root = NULL;
		if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
	}
	void update(int i, int val) {
		if (root == NULL)return;
		update(i, val, root);
	}
	int sumRange(int i, int j) {
		if (root == NULL)return 0;
		return sumRange(i, j, root);
	}
};

本代码提交AC,用时172MS。

LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.


给定一个包含+-*的运算字符串,求所有加括号的方案计算到的值。
采用分治法的思路,尝试在每个操作符分成两个部分,这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归,最后merge。递归的终止条件是当字符串中不包含操作符时,直接返回这个字符串对应的数值。
分治法很经典的例子。
代码如下:

class Solution {
private:
	int operate(int a, int b, char c) {
		switch (c) {
			case '+':return a + b;
			case '-':return a - b;
			case '*':return a*b;
		}
	}
public:
	vector<int> diffWaysToCompute(string input) {
		int n = input.size();
		vector<int> ans;
		bool found = false;
		for (int i = 0; i < n; ++i) {
			if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
				found = true;
				vector<int> lefts = diffWaysToCompute(input.substr(0, i));
				vector<int> rights = diffWaysToCompute(input.substr(i + 1));
				for (int j = 0; j < lefts.size(); ++j) {
					for (int k = 0; k < rights.size(); ++k) {
						ans.push_back(operate(lefts[j], rights[k], input[i]));
					}
				}
			}
		}
		if (!found)return{ atoi(input.c_str()) };
		return ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Search a 2D Matrix II

LeetCode Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.


LeetCode Search a 2D Matrix基础上改动了一点点,但是难度增加不少。这一次,每行和每列都是递增的,但是这一行的行首元素和上一行的行末元素没有大小关系,这种矩阵有点像从左上角递增到右下角的一个曲面,想象一下。
一种比较笨的办法就是对每一行或者每一列二分搜索,复杂度为O(mlgn)或O(nlgm)。
参考这位大神的介绍,有很多厉害的算法,具体看原博客,这里简单给出其前两个算法的C++实现。
算法1相当于对角二分搜索,是线性复杂度的。搜索从矩阵右上角开始,遇到比当前元素大时,递增行;遇到比当前元素小时,递减列;直到找到相等元素,或者到达矩阵左下角。最坏情况是从右上角走到了左下角,复杂度为O(m+n)。

这种思路的代码如下:

class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if (matrix.size() == 0)return false;
		int m = matrix.size(), n = matrix[0].size();
		if (n == 0)return false;
		int i = 0, j = n - 1;
		while (i < m&&j >= 0) {
			while (i < m&&matrix[i][j] < target)++i;
			if (i >= m)return false;
			while (j >= 0 && matrix[i][j] > target)--j;
			if (j < 0)return false;
			if (matrix[i][j] == target)return true;
		}
		return false;
	}
};

本代码提交AC,用时129MS。
算法2利用了分治法的思路。每次取矩阵中心元素,把矩阵分成4个小份。如果target大于中心元素,则左上角部分可以全部舍弃掉,因为矩阵的行列都是递增的,左上角元素肯定全部小于中心元素,不必再找。此时可以递归的在剩余的3个小矩阵里查找。比如下图中心元素为9,如果要找26,则可以递归的在其右上角、左下角和右下角三个小矩阵中查找。

时间复杂度公式为T(n)=3T(n/2)+c,c为target和中心元素比较的时间。使用主方法可以算到T(n)=O(n1.58)。
分治法思路代码如下:

class Solution {
public:
	bool quadPart(vector<vector<int>>& matrix, int left, int top, int right, int bottom, int target) {
		if (left > right || top>bottom)return false;
		if (target<matrix[left][top] || target>matrix[right][bottom])return false;
		int midrow = left + (right - left) / 2, midcol = top + (bottom - top) / 2;
		if (target == matrix[midrow][midcol])return true;
		//if (target > matrix[midrow][midcol]) { // 抛弃左上角
		//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
		//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
		//		quadPart(matrix, midrow, midcol, right, bottom, target); // 右下角
		//}
		//else {
		//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
		//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
		//		quadPart(matrix, left, top, midrow, midcol, target); //左上角
		//}
		if (target > matrix[midrow][midcol]) { // 抛弃左上角
			return quadPart(matrix, left, midcol + 1, midrow, bottom, target) || // 右上角
				quadPart(matrix, midrow + 1, top, right, midcol, target) || // 左下角
				quadPart(matrix, midrow + 1, midcol + 1, right, bottom, target); // 右下角
		}
		else {
			return quadPart(matrix, left, midcol, midrow - 1, bottom, target) || // 右上角
				quadPart(matrix, midrow, top, right, midcol - 1, target) || // 左下角
				quadPart(matrix, left, top, midrow - 1, midcol - 1, target); //左上角
		}
	}
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if (matrix.size() == 0)return false;
		int m = matrix.size(), n = matrix[0].size();
		if (n == 0)return false;
		return quadPart(matrix, 0, 0, m - 1, n - 1, target);
	}
};

本代码提交AC,用时168MS。
注意代码中注释掉的部分是错误代码,因为其在右下角或者左上角搜索时可能会进入死循环。比如要在上图搜索30,当搜索到右下角深色部分的小矩阵时,中心元素是17,本该搜索更小的矩阵30,但是根据注释代码中第一个if搜索右下角的代码,新的矩阵(右下角)的左上角坐标还是17,因为其坐标是(midrow, midcol),无论递归多少次,右下角的矩阵没有变小,所以进入了死循环。
正确的方法是把涉及到中点的两条边分配到不同的小矩阵里,必须使得每个小矩阵的左上角或右下角坐标有变化。

LeetCode Pow(x, n)

LeetCode Pow(x, n)
Implement pow(x, n).


实现幂指数运算。
如果对x连乘n次,时间复杂度为O(n),但使用分治法能降到O(\log n)。因为可以把x^n分解为:

\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}


完整代码如下:

class Solution {
public:
	double doPow(double x, int n) {
		if (n == 0)return 1.0;
		double v = doPow(x, n / 2);
		if (n % 2 == 0)return v*v;
		else return v*v*x;
	}
	double myPow(double x, int n) {
		int m = n > 0 ? n : -n;
		double ans = doPow(x, m);
		return n > 0 ? ans : 1.0 / ans;
	}
};

本代码提交AC,用时3MS。
注意在子程序中不要调用两次doPow(x, n/2),算出一个v,然后直接v*v即可。
二刷。使用非递归的方法实现快速幂,代码如下:

class Solution {
public:
	double myPow(double x, int n) {
		if (n == 0) return 1;
		if (n == 1) return x;
		long long m = n; // 先转换为ll,否则n=INT_MIN是有问题
		m = m > 0 ? m : -m;
		double ans = 1;
		while (m) {
			if (m & 1)ans *= x;
			m >>= 1;
			x = x*x;
		}
		return n > 0 ? ans : 1 / ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Maximum Subarray

LeetCode Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


求最大连续子数组和,这是一道非常经典的题目,从本科时候就开始做了。有两种解法。
动态规划法
用dp数组存储到当前元素的最大子数组和,如dp[i-1]表示包含第i-1个元素的最大子数组和,则dp[i]表示包含第i个元素的最大子数组和。如果dp[i-1]>0,则dp[i]=dp[i-1]+nums[i];否则dp[i]=nums[i]。完整代码如下:

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		vector<int> dp(nums.size(), 0);
		dp[0] = nums[0];
		int ans = nums[0];
		for (int i = 1; i < nums.size(); i++) {
			if (dp[i - 1] > 0)dp[i] = dp[i - 1] + nums[i];
			else dp[i] = nums[i];
			if (dp[i] > ans)ans = dp[i];
		}
		return ans;
	}
};

本代码只用扫描一遍数组,所以时间复杂度为O(n)。本代码提交AC,用时12MS。
分治法
将数组一分为二,比如数组[a,b]分为[a,m-1]和[m+1,b],递归求解[a,m-1]和[m+1,b]的最大连续子数组和lmax和rmax,但是[a,b]的最大连续子数组和还可能是跨过中点m的,所以还应该从m往前和往后求一个包含m的最大连续子数组和mmax,然后再求lmax,rmax,mmax的最大值。完整代码如下:

class Solution {
public:
	int divide(vector<int>& nums, int left, int right) {
		if (left == right)return nums[left];
		if (left == right - 1)return max(nums[left] + nums[right], max(nums[left], nums[right]));
		int mid = (left + right) / 2;
		int lmax = divide(nums, left, mid - 1);
		int rmax = divide(nums, mid + 1, right);
		int mmax = nums[mid], tmp = nums[mid];
		for (int i = mid - 1; i >= left; i--) {
			tmp += nums[i];
			if (tmp > mmax)mmax = tmp;
		}
		tmp = mmax;
		for (int i = mid + 1; i <= right; i++) {
			tmp += nums[i];
			if (tmp > mmax)mmax = tmp;
		}
		return max(mmax, max(lmax, rmax));
	}
	int maxSubArray(vector<int>& nums) {
		return divide(nums, 0, nums.size() - 1);
	}
};

本代码可以类比平面上求最近点对的例子,需要考虑跨界的问题,时间复杂度为O(nlgn)。本代码提交AC,用时也是12MS。
综合来看,还是动态规划法更漂亮。

LeetCode Median of Two Sorted Arrays

LeetCode Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).


这道题很有意思,虽然本科的时候就做过练习题,用二分查找递归的减少数据规模,但是当时只写过伪代码,这次真正写代码提交的时候,发现有很多BUG。
这个题的思路有3种:1)两个数组放一起排序,取中位数O((m+n)lg(m+n));2)用归并排序的方式把他们Merge到一块,取中间数O(m+n),其实边Merge边数数,Merge到(m+n)/2个数的时候就已经是中位数了;3)二分的思路,比较A,B数组的中位数,根据大小关系选择在前半段或后半段继续递归。
我开始尝试了二分的思路,很多测试样例不能通过,要考虑奇偶性等问题也导致代码不够优雅。查看网络发现可以把这一题转换为从两个已排序数组A,B中取第k小的元素的问题,如果是m+n是奇数,则取中间那个数,偶数则取中间两个数求平均。
关于从两个已排序数组A,B中取第k小的元素的问题,这篇文章有较详细的讨论。下面简要讲一下最后一种O(lgm+lgn)的方法。
如果A的某个元素A_i和B的某两个连续元素B_jB_{j-1}有关系B_{j-1}\leq A_i\leq B_j,那么可以确定A_i就是AB合起来的第i+j+1小的元素,因为A_i大于A中前i个元素,A_i又大于B_{j-1},而B_{j-1}又大于B前面j-1个元素,所以在AB合起来的数组中,A_i大于A前面i个元素和B前面j个元素,排在第i+j+1的位置。同理如果A_{i-1}\leq B_j\leq A_i,则B_j是第i+j+1小的元素。
如果我们令k=i+j+1,则可以容易得到第k小的元素。关于i,j的取值问题,理论上i,j可以取任意值,只要满足i+j=k-1就可以了。不过常见的取法是先取i为A的中点,然后取j=k-1-i;或者按A,B元素个数的比例取值,比如上述链接中的代码。
上述链接中给出了如果A,B中不存在相同元素时的代码,如下:

int findKthSmallest(int A[], int m, int B[], int n, int k) {
  assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);
  int i = (int)((double)m / (m+n) * (k-1));
  int j = (k-1) - i;
  assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
  // invariant: i + j = k-1
  // Note: A[-1] = -INF and A[m] = +INF to maintain invariant
  int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
  int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
  int Ai   = ((i == m) ? INT_MAX : A[i]);
  int Bj   = ((j == n) ? INT_MAX : B[j]);
  if (Bj_1 < Ai && Ai < Bj)
    return Ai;
  else if (Ai_1 < Bj && Bj < Ai)
    return Bj;
  assert((Ai > Bj && Ai_1 > Bj) ||
         (Ai < Bj && Ai < Bj_1));
  // if none of the cases above, then it is either:
  if (Ai < Bj)
    // exclude Ai and below portion
    // exclude Bj and above portion
    return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);
  else /* Bj < Ai */
    // exclude Ai and above portion
    // exclude Bj and below portion
    return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);
}

针对本题C++代码如下:

class Solution {
public:
	double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k)//find kth smallest
	{
		int m = nums1.size(), n = nums2.size();
		//always assume that m is equal or smaller than n
		if (m > n)
			return findKthSmallest(nums2, nums1, k);
		if (m == 0)
			return nums2[k - 1];
		if (k == 1)
			return min(nums1[0], nums2[0]);
		//divide k into two parts
		int i = (int)((double)m / (m + n)*(k - 1));
		int j = (k - 1) - i;
		int Ai_1 = ((i == 0) ? INT_MIN : nums1[i - 1]);
		int Bj_1 = ((j == 0) ? INT_MIN : nums2[j - 1]);
		int Ai = ((i == m) ? INT_MAX : nums1[i]);
		int Bj = ((j == n) ? INT_MAX : nums2[j]);
		if (Bj_1 < Ai && Ai < Bj)
			return Ai;
		else if (Ai_1 < Bj && Bj < Ai)
			return Bj;
		if (Ai < Bj)
		{
			vector<int> v1(nums1.begin() + i + 1, nums1.end());
			vector<int> v2(nums2.begin(), nums2.begin() + j);
			return findKthSmallest(v1, v2, k - i - 1);
		}
		else if (Ai > Bj)
		{
			vector<int> v1(nums1.begin(), nums1.begin() + i);
			vector<int> v2(nums2.begin() + j + 1, nums2.end());
			return findKthSmallest(v1, v2, k - j - 1);
		}
		else
			return Ai;
	}
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int total = nums1.size() + nums2.size();
		if (total & 0x01)
			return findKthSmallest(nums1, nums2, total / 2 + 1);
		else
			return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
	}
};

本代码提交AC,用时52MS。
二刷。
上面的解法真的太复杂了,完全记不住。从两个有序数组中求第K大的数,在http://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/有非常详细的解法,归并O(m+n)的解法就不说了。
O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2],如果mid1+mid2arr2[mid2]的情况类似。
如果mid1+mid2>k,说明第K大的数比较小,根据上面的分析,下次递归时,可以舍弃掉[start1,mid1], (mid1,end1], [start2,mid2], (mid2,end2]中较大的那块。比如arr1[mid1]>arr2[mid2],则可以舍弃掉(mid2,end2]。
这样每次都可以舍弃掉两个数组中的某个的一半,时间复杂度是O(lgm+lgn),代码在GeeksforGeeks中。
更优的O(lg(k))的方法是,每次我们不是取中值,而是取arr1[k/2]和arr2[k/2],直接根据这两个值的大小关系去分割递归。代码见GeeksforGeeks中最后一个版本的代码,简洁。
针对这一题,求两个有序数组的中位数,如果两个有序数组的总长度len是奇数,则中位数就是两个有序数组中的第len/2大数;如果len是偶数,则中位数是第len/2和len/2的平均数,所以最多需要两次调用findKth就可以得到结果。完整代码如下:

class Solution {
    private:
    int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k) {
        int len1 = e1 - s1 + 1, len2 = e2 - s2 + 1;
        if(len1 > len2)
            return findKth(nums2, s2, e2, nums1, s1, e1, k);
        if(len1 == 0)
            return nums2[s2 + k - 1];
        if(k == 1)
            return min(nums1[s1], nums2[s2]);
        int i = s1 + min(k / 2, len1) - 1, j = s2 + min(k / 2, len2) - 1;
        if(nums1[i] > nums2[j])
            return findKth(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1));
        else
            return findKth(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1));
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if((m + n) % 2) {
            return findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1);
        } else {
            return (findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2) + findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1)) / 2.0;
        }
    }
};

本代码提交AC,用时65MS。

hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案
#1139 : 二分·二分答案
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回和上上回里我们知道Nettle在玩《艦これ》,Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。
在这个游戏里面,海域是N个战略点(编号1..N)组成,如下图所示

其中红色的点表示有敌人驻扎,猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点,虚线表示各个战略点之间的航线(无向边)。
在游戏中要从一个战略点到相邻战略点需要满足一定的条件,即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。
由于提高索敌值需要将攻击机、轰炸机换成侦察机,舰队索敌值越高,也就意味着舰队的战力越低。
另外在每一个战略点会发生一次战斗,需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗,所以舰队最多只能走过K条航路。
现在Nettle想要以最高的战力来进攻boss点,所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路,使得舰队需要达到的索敌值最低,并且有剩余的燃料和子弹。
特别说明:两个战略点之间可能不止一条航线,两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。
提示:你在找什么?
输入
第1行:4个整数N,M,K,T。N表示战略点数量,M表示航线数量,K表示最多能经过的航路,T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000
第2..M+1行:3个整数u,v,w,表示战略点u,v之间存在航路,w表示该航路需求的索敌值,1≤w≤1,000,000。
输出
第1行:一个整数,表示舰队需要的最小索敌值。
样例输入
5 6 2 5
1 2 3
1 3 2
1 4 4
2 5 2
3 5 5
4 5 3
样例输出
3


本题的目标是在无向图中,求从点1到T的路径中的索敌值的最大值的最小值,且经过的路径不能超过k段。
在输入的时候,我们能得到所有索敌值的最大值high和最小值low,high值显然能够成功到达T点,且不超过k段,因为题目说了保证至少存在一条路径能在燃料子弹用完前到达boss点;low就不一定了。所以二分答案的意思就是在区间[low,high]中二分查找最小可行解。
假设函数f(x)能判断当索敌值为x时,是否能成功到达T点且不超过k段。则每二分一次就求一次f(mid),根据f(mid)的值调整区间[low,high]的端点。所以现在的关键就是函数f(x)。
f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图,有可能TLE或MLE,使用邻接表更好。完整代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005;
vector<vector<int>> path;
vector<vector<int>> powers;
vector<bool> visit;
int n, m, k, t;
bool BFS(int power)
{
	visit.clear();
	visit.resize(n + 1, false);
	queue<int> Q;
	int u, v, len = 0;;
	Q.push(1);
	visit[1] = true;
	Q.push(-1);
	while (!Q.empty()&&len<k)
	{
		u = Q.front();
		Q.pop();
		if (u == -1)
		{
			if (Q.empty())
				return false;
			else
			{
				len++;
				Q.push(-1);
				continue;
			}
		}
		for (int i = 0; i < path[u].size(); i++)
		{
			v = path[u][i];
			if (!visit[v]&&powers[u][i] <= power)
			{
				if (v == t)
					return true;
				visit[v] = true;
				Q.push(v);
			}
		}
	}
	return false;
}
int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %d %d %d", &n, &m, &k, &t);
	path.resize(n + 1);
	powers.resize(n + 1);
	int u, v, w, low = kMaxW, high = 0;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
		low = min(low, w);
		high = max(high, w);
		path[u].push_back(v);
		path[v].push_back(u);
		powers[u].push_back(w);
		powers[v].push_back(w);
	}
	while (low+1 < high)
	{
		int mid = (low + high) / 2;
		if (BFS(mid))
			high = mid;
		else
			low = mid;
	}
	printf("%d\n", high);
	return 0;
}

在BFS的时候可以单独保存每个点及该点此时的深度(len),也可以共用一个len,只需额外加入一个标记-1,当碰到-1时,说明已经遍历完一层了,深度加1。
本代码提交AC,用时189MS,内存8MB。

hihoCoder 1133-二分·二分查找之k小数

hihoCoder 1133-二分·二分查找之k小数
#1133 : 二分·二分查找之k小数
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回里我们知道Nettle在玩《艦これ》,Nettle的镇守府有很多船位,但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船,但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久,决定随机选择一个k,然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度,Nettle现在把所有船的稀有度值告诉你,希望你能帮他找出目标船。
提示:非有序数组的二分查找之二
输入
第1行:2个整数N,k。N表示数组长度,
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。
输出
第1行:一个整数t,表示t在数组中是第k小的数,若K不在数组中,输出-1。
样例输入
10 4
1732 4176 2602 6176 1303 6207 3125 1 1011 6600
样例输出
1732


给定一个无序序列,问序列中第k小的数是哪个。简单粗暴的方法是排序直接取a[k],复杂度为O(nlgn);还有一种O(lgn)的方法,采用了和hihoCoder 1128-二分·二分查找类似的方法,将序列不断二分成小于某个数和大于某个数的两部分,直到某一部分长度为k。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n, k;
vector<int> a;
int GetNumberK(int p, int q)
{
	int m = a[p], i = p, j = q;
	while (i < j)
	{
		while (i < j&&a[j] > m)
			j--;
		a[i] = a[j];
		while (i < j&&a[i] < m)
			i++;
		a[j] = a[i];
	}
	if (k == i + 1)//(1)
		return m;
	else if (k < i + 1)
		return GetNumberK(p, i - 1);
	else
	{
		//k = k - (i - p + 1);//(2),因为(1)处判等的时候i取p,但分割之后p并没有从0开始,所以k还是k
		return GetNumberK(i + 1, q);
	}
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	a.resize(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (k > n||k < 1)
		printf("-1\n");
	else
		printf("%d\n", GetNumberK(0, n - 1));
	return 0;
}

本代码提交AC,用时69MS,内存3MB。
需要注意一点,代码中(2)不能出现,虽然递归在[i+1,q]内部查找第k - (i - p + 1)小的数,但是(1)处判等的时候,使用的i(即p)是相对[0,n-1]长度的,所以这里的k不需要剪短

hihoCoder 1128-二分·二分查找

hihoCoder 1128-二分·二分查找
#1128 : 二分·二分查找
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Nettle最近在玩《艦これ》,因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金,开了无数个船位)。去除掉重复的船之后,还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值,任意两艘船的稀有值都不相同,稀有值越小的船越稀有,价值也就越高。
Nettle现在通过大建又造出了一艘船,他想知道这艘船是不是重复的。如果是重复的,那么这艘船在Nettle所有的船里面稀有值排多少位。
问题一
Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N]),我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中,且有对应的a[i]=K时,i为多少?
提示一:有序数组的二分查找
问题二
因为Nettle的船太多了,他不愿意去给所有船按照稀有值排序,而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢?
提示二:非有序数组的二分查找
输入
第1行:2个整数N,K。N表示数组长度,K表示需要查找的数;
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。
输出
第1行:一个整数t,表示K在数组中是第t小的数,若K不在数组中,输出-1。
样例输入
10 5180
2970 663 5480 4192 4949 1 1387 4428 5180 2761
样例输出
9


给出一串数字,问某个数字K在该序列中是第几小的。
最简单的解法,遍历一遍数组,找出比K小的数的个数n,则K是第n+1小的数。完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int main()
{
	scanf("%d %d", &n, &k);
	a.resize(n);
	bool is_exist = false;
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] == k)
			is_exist = true;
		if (a[i] < k)
			ans++;
	}
	if (!is_exist)
		printf("-1\n");
	else
		printf("%d\n", ans + 1);
	return 0;
}

本代码提交AC,用时58MS,内存3MB。
但是题意显然不是用这种方法,为了配合下一题的求第k小数,提示使用快排的中间步骤,依次将序列划分成比某个数大和比某个数小的两部分,再在其中某个子序列中递归求解。完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int GetOrder(int p, int q)
{
	int m = a[p];
	int i = p, j = q;
	while (i < j)
	{
		while (i < j&&a[j] > m)
			j--;
		a[i] = a[j];
		while (i < j&&a[i] < m)
			i++;
		a[j] = a[i];
	}
	if (k == m)
		return i;
	else if (k < m)
		return GetOrder(p, i - 1);
	else
		return GetOrder(i + 1, q);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	a.resize(n);
	bool is_exist = false;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] == k)
			is_exist = true;
	}
	if (!is_exist)
		printf("-1\n");
	else
		printf("%d\n", GetOrder(0, n - 1) + 1);
	return 0;
}

本代码提交AC,用时57MS,内存3MB。

hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临
#1070 : RMQ问题再临
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢?
于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢?
提示:平衡乃和谐之理
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。
每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi
对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。
样例输入
10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5
样例输出
1923
2009
1020
1923


本题的数据量比hihoCoder Problem 1068: RMQ-ST 算法这题要小,虽然

用O(N)的时间进行计算——扫描一遍整个区间找到最小值,然后对于每一个更改操作,使用O(1)的时间直接进行修改,这样也就是O(NQ)的总时间复杂度!在这种数据量下完全是可以通过的!

但是本题希望我们用线段树来解决。
我曾在《数据结构》的改造红黑树中看到过区间树,但是本题的线段树和书中的区间树有所区别,区间树由红黑树改造而来,结构更复杂些,这里只需要使用线段树即可。
常规的线段树如下图所示:

从图中可以看到构造线段树的过程就是一个二分的过程,不断将区间分成两半,直到只有一个元素。图中的线段树每一个节点是一个区间[l,r],本题我稍微改造了一下,改成了数组int seg_tree[left][length],比如seg_tree[i][j]表示从下标i开始,长度为j的这样一个区间上的最小值,这样就可以利用线段树来解决RMQ问题了。比如改造后的线段树就成了下面的样子:

因为树形这种特殊的结构,我们可以用一个DFS来对树实现二分构造,当DFS到某个节点长度为1时,其最小值就是w[i]本身,在回溯到父节点时,父节那个区间的最小值又是所有子节点最小值中的最小值。因为树的总节点数大约为2*n,所以复杂度O(n)。
当需要查询区间[l,r]的最小值时,只需对数组seg_tree二分搜索。具体来说,假设我们搜索到了节点[s_l,s_len],如果r<(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的左边,我们递归在[s_l,s_len/2]区间找;如果l>=(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的右边,我们递归在[s_l+s_len/2,s_len-s_len/2]区间找;如果以上两者都不是,说明[l,r]跨界了,而且中点下标一定是s_l+s_len/2,所以我们分别在二两半区间找,然后求这两者的最小值。复杂度O(lgn)。
当需要更新某个下标为pos的值为value时,也是DFS查找线段树,直到找到叶子seg_tree[pos][1],更新它的值,以及所有我们在查找过程经过的父节点的值。复杂度O(lgn)。
所以线段是的性质使得无论是构造、查询、更新操作,复杂度都只要O(lgn),这就是题目中所说的把总的复杂度平均分配到不同操作:平衡乃和谐之理。
完整代码如下:

#include<iostream>
using namespace std;
const int MAX_N=1e4+2;
int w[MAX_N];//每个商品重量
int n,m;
int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]:起点为i,长度为j的区间的最小值
inline int get_min(int a,int b)
{
     return a<b?a:b;
}
//深度优先遍历以构造线段树
void dfs(int left,int length)
{
     if(length==1)
     {
          seg_tree[left][1]=w[left];
          return;
     }
     dfs(left,length/2);
     dfs(left+length/2,length-length/2);
     seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值
}
//在区间[s_left,s_len]搜索区间[left,length]的最小值
int search_min(int s_left,int s_len,int left,int length)
{
     if((s_left==left)&&(s_len==length))
          return seg_tree[s_left][s_len];
     if((left+length-1)<(s_left+s_len/2))//全在左半部分
     {
          return search_min(s_left,s_len/2,left,length);
     }
     else if(left>=(s_left+s_len/2))//全在右半部分
     {
          return search_min(s_left+s_len/2,s_len-s_len/2,left,length);
     }
     else//左右分开搜索
     {
          int left_len=s_left+s_len/2-left;
          int right_len=length-left_len;
          int min_left=search_min(s_left,s_len/2,left,left_len);
          int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len);
          return get_min(min_left,min_right);
     }
}
//从区间[s_left,s_len]开始更新下标pos的值为value
void update(int s_left,int s_len,int pos,int value)
{
     if((s_left==pos)&&(s_len==1))
     {
          seg_tree[s_left][1]=value;
          return ;
     }
     int mid=s_left+s_len/2;
     if(pos<mid)
          update(s_left,s_len/2,pos,value);
     else
          update(mid,s_len-s_len/2,pos,value);
     seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     for(int i=1;i<=n;i++)
          cin>>w[i];
     dfs(1,n);
     cin>>m;
     int p,l,r;
     for(int i=0;i<m;i++)
     {
          cin>>p>>l>>r;
          if(p==0)//查询
          {
               cout<<search_min(1,n,l,r-l+1)<<endl;
          }
          else//修改
          {
               update(1,n,l,r);
          }
     }
     return 0;
}

本代码提交AC,用时151MS,内存42MB。