[hihoCoder] #1305 : 区间求差 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
Read full article from [hihoCoder] #1305 : 区间求差 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
给定两个区间集合 A 和 B，其中集合 A 包含 N 个区间[ A1, A2 ], [ A3, A4 ], ..., [ A2N-1, A2N ]，集合 B 包含 M 个区间[ B1, B2 ], [ B3, B4 ], ..., [ B2M-1, B2M ]。求 A - B 的长度。
例如对于 A = {[2, 5], [4, 10], [14, 18]}, B = {[1, 3], [8, 15]}, A - B = {(3, 8), (15, 18]}，长度为8。
输入
第一行：包含两个整数 N 和 M (1 ≤ N, M ≤ 100000)。
第二行：包含 2N 个整数 A1, A2, ..., A2N (1 ≤ Ai ≤ 100000000)。
第三行：包含 2M 个整数 B1, B2, ..., B2M (1 ≤= Bi ≤ 100000000)。
输出
一个整数，代表 A - B 的长度。
- 样例输入
3 2 2 5 4 10 14 18 1 3 8 15
- 样例输出
8
思路: 给定两个区间数组, 让求A - B区间的长度是多少, 即A区间去掉重合的B区间还剩多少. 因为A和B本身就有重合的, 因此我们需要先对各自区间进行合并, 然后再求出A和B重合的部分, 剩下的A的长度即是我们要的答案.
vector<pair<int, int> > merge(vector<pair<int, int> >& nums)
{
vector<pair<int, int> > result;
int len = nums.size(), begin = nums[0].first, end = nums[0].second;
for(int i =1; i< len; i++)
{
if(nums[i].first <= end) end = max(end, nums[i].second);
else
{
result.push_back(make_pair(begin, end));
begin = nums[i].first;
end = nums[i].second;
}
}
result.push_back(make_pair(begin, end));
return result;
}
int main()
{
int N, M, val1, val2;
cin>> N >> M;
vector<pair<int, int> > A(N), B(M);
for(int i =0; i< N; i++)
{
cin>>val1 >> val2;
A[i] = make_pair(val1, val2);
}
for(int i =0; i< M; i++)
{
cin>>val1 >> val2;
B[i] = make_pair(val1, val2);
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
vector<pair<int, int> > vecA = merge(A);
vector<pair<int, int> > vecB = merge(B);
int begin, end, ans = 0, k =0, lenA = vecA.size(), lenB = vecB.size();
for(int i = 0; i < lenA; i++)
{
int sum = 0;
begin = vecA[i].first, end = vecA[i].second;
while(k < lenB && vecB[k].second <= begin) k++;
while(k < lenB && vecB[k].second > begin && vecB[k].first < end)
{
sum += min(end, vecB[k].second) - max(begin, vecB[k].first);
k++;
}
if(k >0 && vecB[k-1].second > end) k--;
ans += end-begin - sum;
}
cout << ans << endl;
return 0;
}
Read full article from [hihoCoder] #1305 : 区间求差 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
