POJ1716(Integer Intervals)_NENUOJ(整数区间)_C++版@FDDLC

发布时间：2020-12-15 04:49:01 所属栏目：百科来源：网络整理

导读：POJ1915：http://poj.org/problem?id=1716 NENUOJ：http://47.106.114.75/contest/24/problem/E Description An integer interval [a,b],a Write a program that: finds the minimal number of elements in a set containing at least two different integer

POJ1915：http://poj.org/problem?id=1716

NENUOJ：http://47.106.114.75/contest/24/problem/E

Description

An integer interval [a,b],a < b,is a set of all consecutive integers beginning with a and ending with b.?

Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n,1 <= n <= 10000. Each of the following n lines contains two integers a,b separated by a single space,0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

3 6

2 4

0 2

4 7

Sample Output4?#include #include //用到了vector#include //用到了sortusing namespace std; //以上两个头文件都是C++特有的，而C没有struct node{int left,right;};bool ascending_order(node node_1,node node_2) //用于sort，按升序排列{return node_1.right < node_2.right;}int main(){int n; //行数scanf("%d",&n); //此行不能与下一行交换位置！！！vector node_vector(n); //n必须先输入再使用for(int index = 0; index < n; index++)scanf("%d%d",&node_vector[index].left,&node_vector[index].right);sort(node_vector.begin(),node_vector.end(),ascending_order); //排序，不能写成ascending_order()int former = node_vector[0].right - 1; //假如排完序后第一个区间为[3,6]，则former = 5,latter = 6int latter = node_vector[0].right;int cnt = 2; //用于计数，当前已有两个数for(int index = 1; index < n; index++) //注意：因为前面已经考虑了node_vector[0]，故这里index从1开始{//有3种情况：former、latter两个都在当前区间；一个在；零个在。(一个在:只有latter在former不在这一种情况)if(latter >= node_vector[index].left && former < node_vector[index].left) //一个在{former = latter;latter = node_vector[index].right;cnt++; //只增加了一个数}else if(latter < node_vector[index].left) //两个都不在{former = node_vector[index].right - 1;latter = node_vector[index].right;cnt += 2; //增加了两个数}}//两个都在时啥也不用干，故只考虑两种情况就行printf("%dn",cnt);return 0;}?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!