首页 > 题解 > luogu2519 [HAOI2011]problem a

luogu2519 [HAOI2011]problem a

题目描述

一次考试共有n个人参加,第i个人说:“有ai个人分数比我高,bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

输入输出格式

输入格式:

第一行一个整数n,接下来n行每行两个整数,第i+1行的两个整数分别代表ai、bi

输出格式:

一个整数,表示最少有几个人说谎

输入输出样例

输入样例#1:

3
2 0
0 2
2 2

输出样例#1:

1

说明

100%的数据满足: 1≤n≤100000 0≤ai、bi≤n

题解

假如有a个人比他高,b个人比他低,那就有n-a+b个人和他一样的。。

把这段人看成一条线段,如果有t个人说的x,y相同,那么这条线段的权重就为t。

那么问题就变成了:有m条线段,每个线段有一个权,求使每条线段长度互不相交的前提下权值最大。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×