蓝桥杯-打折

用户10271432

发布于 2023-10-16 19:55:12

1470

发布于 2023-10-16 19:55:12

文章被收录于专栏：机器学习-大数据机器学习-大数据

没有白走的路，每一步都算数🎈🎈🎈

题目描述：

已知小蓝需要购买n个不同的物品，每个物品只需要购买一件，在小蓝家附近有m个商店，每个商店只在特定的时间才会对商店里的所有商品打折，但是小蓝太懒了，只选择一天出去购物买到所有的物品，请问是否可以找到一个最小花费的价钱，满足小蓝离谱的要求。

输入描述：

第一行：

输入两个数据n,m

接下来的m组数据：

第一行有四个数据，s,t,p,c分表代表商店优惠的起始时间和终止时间，p表示打多少折，例如p等于88就表示打88折，c表示商店里面有小蓝所需的商品的种类的个数

接下来的c行数据，每行两个数据，第一个数表示商品的种类，第二个数据表示商品的价格

输出描述：

输出最终的价格

样例输入输出：

样例输入:

2 2 1 2 89 1 1 97 3 4 77 1 2 15

样例输出：

101

算法：

建立一个prime数组，用来存放每个商品的优惠时间段，对应的初始价格，对应的打着率。接着for循环遍历时间，因为不同时间段每个商家是否优惠是不一样的。在这个时间区间，就给商品打折，不在就加原来的价格，一次遍历每一天，得到每次的最小值，输出最小值

算法思路讲解：

读懂题目意思之后，很容易就能发现，暴力能出结果

代码：

n,m = map(int,input().split())
prime = [[]for i in range(n)]#初始未打折的价格
min_s = 100000000
max_t = 0
for i in range(m):
    s,t,p,c = map(int,input().split())
    if s<min_s:
        min_s = s
    if t>max_t:
        max_t = t
    day = [s,t] #存放打折的天数
    for j in range(c):
        a,b = map(int,input().split())
        prime[a-1].append([day,b,p])              
ans = float("inf")
for i in range(min_s,max_t+1):
    tmp = 0
    for j in range(0,n):             
        t = float('inf')
        for k in range(len(prime[j])):
            d1,d2 = prime[j][k][0]
            if d1<=i<=d2:
                t = min(t,prime[j][k][1]*prime[j][k][2]//100)
            else:
                t = min(t,prime[j][k][1])
        tmp+=t
    if tmp<ans:
        ans = tmp
print(ans)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-15，如有侵权请联系 cloudcommunity@tencent.com 删除

range