5496: BZOJ1496:[NOI2006]千年虫
Memory Limit:259 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
千年虫是远古时代的生物,时隔几千万年,千年虫早已从地球上销声匿迹,人们对其知之甚少。考古生物学家最近 开始对其有了兴趣,因为一批珍贵的千年虫化石被发现,这些化石保留了千年虫近乎完整的形态。理论科学家们根 据这些化石归纳出了千年虫的一般形态特征模型,并且据此判定出千年虫就是蜈蚣的祖先!但科学家J发现了实际 与理论的一些出入,他仔细的研究了上百个千年虫化石,发现其中大部分千年虫的形态都不完全符合理论模型,这 到底是什么因素造成的呢?理论科学家K敏锐的指出,千年虫的形态保存在化石中很有可能发生各种变化,即便最 细微的变化也能导致它不符合模型。于是,摆在科学家面前的新问题诞生了:判断一个化石中的千年虫与理论模型 的差距有多大?具体来说,就是根据一个千年虫化石的形态A,找到一个符合理论模型的形态B,使得B是最有可能 在形成化石时变成形态A。
输入格式
第一行为一个整数n; 以下n行,每行两个整数,其中第i行为两个整数L’i,R’i,用一个空格分开; 保证输入数 据合法。n≤1000000, 0≤L’i≤R’i≤1000000
输出格式
仅一行,为一个整数,表示最少代价。
样例输入
7 4 4 3 4 3 5 1 3 2 2 2 4 3 3
样例输出
3
提示
题目来源
没有写明来源