M19963: 买学区房

math, sortings, http://cs101.openjudge.cn/practice/19963

小明同学的家长为了让小明同学接受更好的教育，最近在考虑买某重点中学附近的房子，已知他们买房子要考虑两个因素：房子离学校的距离，以及房子的价格。现在他们有一系列备选的房子，已知这些房子距离学校的x方向距离和y方向距离，以及每栋房子的价格。小明的家长认为，只有同时满足了以下两个条件的房子H买了才是不亏的：

1.小明的家长比较精打细算，所以房子的性价比大于所有备选房子性价比的中位数（定义见下图） 2.小明的家长想攒钱，所以房子的价格小于所有备选房子价格的中位数

注：性价比 = 房子和学校之间的交通距离 / 房子的价格（由于该城市的街道布局接近方格状，且从学校到房子无法穿墙而过，房子H去学校的交通距离定义为，房子H距离学校的x方向距离和y方向距离的和）

现在需要你来帮小明的家长判断，一系列备选房子里，值得买的房子有多少栋。

输入

第1行为1个整数，n，代表备选房子的数目第2行为n个房子离学校的x，y距离对，如“(x,y)”，距离均为整数第3行为n个整数，代表每个房子的价格

输出

一个整数，代表n个房子中值得买的房子数目。

样例输入

Sample1 Input:
5
(100,200) (50,50) (100,300) (150,50) (50,50)
100 300 200 400 500

Sample1 Output:
2

说明：共有5个房子备选，离学校的交通距离分别是100+200=300，50+50=100，100+300=400，150+50=200，50+50=100。这些房子的性价比依次为300/100=3， 100/300=1/3， 400/200=2， 200/400=0.5， 100/500=0.2，中位数是0.5，满足第1个条件的只有第1个和第3个房子。这些房子的价格中位数是300，因此满足第2个条件的只有第1个和第3个房子。所以同时满足两个条件的有第1个和第3个房子，输出2.

样例输出

Sample2 Input:
3
(10,90) (20,180) (30,270)
100 200 300

Sample2 Output:
0

说明：共有三个房子备选，离学校的交通距离分别是10+90=100，20+180=200，30+270=300。这些房子性价比依次为100/100=1，200/200=1，300/300=1，中位数是1，没有房子满足第1个条件，因此不用考虑第二个条件，输出一定是0.

提示

求中位数,要先进行数据的排序（从小到大）,然后计算中位数的序号,分数据为奇数与偶数两种来求.排序时,相同的数字不能省略. 如果总数个数是奇数的话,按从小到大的顺序,取中间的那个数. 如果总数个数是偶数的话,按从小到大的顺序,取中间那两个数的平均数.

同学发现测试数据结尾多空格。可以这样来接收数据： pairs = [i[1:-1] for i in input().split()] distances = [ sum(map(int,i.split(','))) for i in pairs]

来源：cs101 2019 Final Exam

思路：筛选价格小于中位数且性价比（距离/价格）大于中位数的房子。可以使用 statistics.median来计算中位数。

python

import statistics

n = int(input())
# 解析 (x,y) 格式的距离
pairs = [i[1:-1] for i in input().split()]
distances = [sum(map(int, i.split(','))) for i in pairs]
prices = list(map(int, input().split()))
ratios = [d / p for d, p in zip(distances, prices)]


def mid(n, lis):
    lis = sorted(lis)
    if n % 2 == 1:
        return lis[n // 2]
    else:
        return (lis[n // 2 - 1] + lis[n // 2]) / 2


m_price = mid(n, prices)
m_ratio = mid(n, ratios)
# 使用 statistics 库计算中位数更便捷且稳健
# m_price = statistics.median(prices)
# m_ratio = statistics.median(ratios)

ans = 0
for i in range(n):
    if ratios[i] > m_ratio and prices[i] < m_price:
        ans += 1
print(ans)

M19963: 买学区房 ​

M19963: 买学区房