POJ 1716 Integer Intervals_专业打酱油_百度空间
(发发同学讲的)首先把所有的区间按照ending从小到大排序,如果ending相同,start靠前的放在前面。貌似pair不是很符合啊。。
所以我们用greater来给pair排序,然后再reserve一下……
然后呢,就是贪婪了,每次都在各个区间的交集那儿取(因为这样可以让取到的元素属于尽可能多的区间),对于两端的区间,如果交集那儿没取够两个,那就随便再取几个(如果还差1个就取1个,如果差两个就取两个)补上。
其实。。看看贪的方法就能看出来。。给vec一个reserve或者不给reserve都是一样的…… 因为中间的那些交集不管是否reserve都是不变的,无非是两边取的时候有点区别。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <memory.h>

using namespace std;

int
main()
{
vector<pair<int, int> > vec;
int nr_intervals;
int seg_begin(0x7FFFFFFF), seg_end(0);
int previous1, previous2;
int nr_elements(0);

//freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);

cin >> nr_intervals;
for (int i = 0; i != nr_intervals; ++i) {
int t1, t2;

cin >> t1 >> t2;
seg_begin = min(t1, seg_begin);
seg_end = max(t2, seg_end);
vec.push_back(make_pair(t1, t2));
}

sort(vec.begin(), vec.end(), greater<pair<int, int> >());
vec.reserve(vec.size());

previous1 = vec.front().first;
previous2 = vec.front().first + 1;
nr_elements = 2;
for (vector<pair<int, int> >::iterator iter = vec.begin() + 1, iter_end = vec.end(); iter != iter_end; ++iter) {
// Obviously, previous2 > previous1.
if (iter->second < previous1) {
// None in our set is included by range *iter.
nr_elements += 2;
previous1 = iter->first;
previous2 = iter->first + 1;
} else if (iter->second < previous2) {
// It is easy to figure out that iter->second is larger or equal to previous1 if we get here.
nr_elements += 1;
previous2 = previous1;
previous1 = iter->first;
} // Or the entire range specified by *iter is satisfied by our set.
}

cout << nr_elements << endl;

return 0;
}


郑重声明:资讯 【POJ 1716 Integer Intervals_专业打酱油_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——