做耳标网站,郓城做网站哪家好,福州百度代理,东莞seo推广优化排名eating
题目背景
从前有个荣光的王国#xff0c;小 A 是里面的国王#xff0c;今天他要赐予他的子民以仓廪。
题目描述
在一条街上有 n n n 个饭店。小 A 站在这条街的最左端。
第 i i i 个饭店离这条街最左端的距离是 a i a_i ai#xff0c;它所售卖的菜品的美味…eating
题目背景
从前有个荣光的王国小 A 是里面的国王今天他要赐予他的子民以仓廪。
题目描述
在一条街上有 n n n 个饭店。小 A 站在这条街的最左端。
第 i i i 个饭店离这条街最左端的距离是 a i a_i ai它所售卖的菜品的美味值是 b i b_i bi。
小 A 不想走太多路但是又想吃到好吃的东西。因此他定义一个饭店的吸引力是 w i b i a i w_i \frac{b_i}{a_i} wiaibi。
小 A 想知道吸引力最大的饭店的编号是多少。如果有多个吸引力最大的饭店你要告诉他距离街道左端距离最近的那个饭店的编号。
输入格式
第一行是一个整数 n n n表示商店的个数。 接下来 n n n 行每行两个整数表示一个商店离街道左端的距离 a i a_i ai 个菜品美味值 b i b_i bi。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
3
1 2
2 4
3 9样例输出 #1
3样例 #2
样例输入 #2
3
1 2
2 3
3 4样例输出 #2
1样例 #3
样例输入 #3
3
1 1
2 3
4 6样例输出 #3
2提示
数据规模与约定
对 20 % 20\% 20% 的数据 n 2 n 2 n2。对 40 % 40\% 40% 的数据保证 b i b_i bi 是 a i a_i ai 的倍数。对 60 % 60\% 60% 的数据保证给出的 a i a_i ai 单调递增。对 80 % 80\% 80% 的数据保证 n ≤ 1000 n \leq 1000 n≤1000。对 100 % 100\% 100% 的数据保证 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2≤n≤105 1 ≤ a i , b i ≤ 1 0 9 1 \leq a_i, b_i \leq 10^9 1≤ai,bi≤109 a i a_i ai 互不相同。
为了解决这个问题我们可以遍历所有的饭店计算每个饭店的吸引力 w i b i a i w_i \frac{b_i}{a_i} wiaibi并记录当前最大的吸引力和对应的饭店编号。如果有多个饭店的吸引力相同且都是最大的我们还需要记录这些饭店中距离街道左端最近的饭店编号。
以下是具体的Python代码实现
n int(input().strip()) # 读取饭店数量
max_attraction float(-inf) # 初始化最大吸引力为负无穷
closest_restaurant 0 # 初始化距离街道左端最近的饭店编号为0实际上这个初始值不会被使用
answer 0 # 初始化答案为0实际答案会在这个基础上更新for i in range(n):a_i, b_i map(int, input().strip().split()) # 读取每个饭店的距离和美味值w_i b_i / a_i # 计算吸引力# 如果当前饭店的吸引力大于已知的最大吸引力if w_i max_attraction:max_attraction w_i # 更新最大吸引力answer i 1 # 更新答案为当前饭店的编号# 如果当前饭店的吸引力等于已知的最大吸引力但距离更近elif w_i max_attraction and a_i min(a_i for _, a_i in enumerate(range(answer-1, -1, -1))):# 注意这里我们假设answer-1之前的饭店的a_i都已经被读取过了但实际上我们需要一个额外的数据结构来存储这些值# 但由于题目保证a_i互不相同我们可以直接更新answer因为更近的饭店一定在更前面被读取answer i 1 # 更新答案为当前饭店的编号print(answer) # 输出答案然而上面的代码在处理距离更近的饭店时存在逻辑上的不严谨因为我们在遍历过程中并没有存储之前所有饭店的距离。但由于题目保证 a i a_i ai 互不相同我们可以简化处理当遇到吸引力相同的饭店时我们直接更新答案因为后读取的饭店即距离更近的会覆盖之前的答案。
下面是简化后的代码
n int(input().strip())
max_attraction float(-inf)
answer 0for i in range(n):a_i, b_i map(int, input().strip().split())w_i b_i / a_iif w_i max_attraction or (w_i max_attraction and i 1 answer):max_attraction w_ianswer i 1print(answer)这样我们就可以正确地找到吸引力最大且距离街道左端最近的饭店编号了。
