我们需要把 2n
个人分成两组,各有 n
人,分别去桂林象鼻山(记作 A)和张家界(记作 B),使总费用最小。
经典做法是“差值排序(贪心)”:
对每个人计算差值 d = a_i - b_i
(去 A 与去 B 的费用差)。
将所有人按 d
从小到大排序:
n
人分配给 A。n
人分配给 B。小红是一家游戏开发公司的老板,他的公司正在开发一款的开放世界冒险游戏。这款游戏的主角是一位拥有神奇能力的少年,他要在一个充满奇幻和危险的世界中寻找自己的身世和命运。游戏中有两个重要的地区,分别是桂林象鼻山和张家界,它们分别代表了水和火的元素,也是游戏中的两大势力的所在地。
桂林象鼻山是一个美丽而神秘的地方,它被人们称为桂林山水的象征。象鼻山因酷似一只站在江边伸鼻豪饮漓江甘泉的巨象而得名象鼻山,它是桂林的城徽山,也是桂林旅游的标志山。在游戏中,象鼻山是水之国的首都,水之国是一个以智慧和文化为荣的国家,它拥有强大的水系魔法和先进的科技。水之国的人民信仰普贤菩萨,他们在象鼻山上建造了一座普贤塔,作为他们的精神象征。水之国与火之国有着悠久的历史纠葛,两国经常发生冲突和战争。
张家界是一个壮观而惊险的地方,它以其奇峰林立、云雾缭绕、风光秀丽而闻名于世。在游戏中,张家界是火之国的领土,火之国是一个以勇敢和力量为傲的国家,它拥有强大的火系魔法和精湛的武艺。火之国的人民信仰龙神,他们在张家界中建造了一座龙神殿,作为他们的崇拜场所。火之国与水之国有着深仇大恨,两国经常进行残酷和无情的斗争。
为了提高游戏的质量和真实感,小红决定派遣 2×n 个员工,分别前往游戏中的两个地区的现实参考地:桂林象鼻山和张家界,进行实地考察和采集素材。每个地区都需要 n 个员工,但是由于不同的交通方式和住宿条件,每个员工到达两个地区的费用不尽相同。小红想要尽可能节省开支,所以他需要找到一种最优的分配方案,使得总费用最小。
你可以编程帮助小红解决这个问题吗?
输入第一行为一个整数 n(1≤n≤1e5) ,表示每个目的地需要 n 个人;
接下来 2∗n 行,每行两个整数,第 i 行为两个整数 ai 和 bi ,表示第 i 个人去桂林象鼻山的路费和去张家界的路费。
(1≤ai,bi≤1e5)
输出为一个整数,表示最小路费开销。
输入
2
20 10
200 30
50 400
20 30
输出
110
样例说明
110=10+30+50+20
输入
2
48 86
50 38
93 99
45 9
输出
188