美团-算法-笔经

一.小美的评分计算器
美团对于商家的评价体系是1-5星评价体系，用户在完成订单之后可以对商家打1/2/3/4/5星，而在客户端上，商家的评级却不一定是整数，而是会显示小数点后的一位。很显然这就需要一个计算器了，小美拥有了一些商户的评价数据，希望可以计算出商家在客户端上显示出的评分。
这个评分的计算非常简单，就是对该商家的所有客户的星级评价做求一个平均，然后去尾法显示小数点后的一位即可，例如平均得分是3.55，则显示的是3.5。例如某商家获得了1-5星评价各一个，则显示的评分是(1+2+3+4+5)/5=3.0。
如果商家没有获得评价，则显示0.0。

输入描述
输入包含5个整数，依次分别表示商家获得1星到5星的评价数量，每一种评价的数量都不大于1000。
输出描述
输出仅包含一个保留一位的小数，表示商家在客户端上显示的评级。

样例输入
2 2 1 1 2
样例输出
2.8

AC

ls = list(map(int,input().split()))
res=0
num=0
for i in range(1,6):
    res+=i*ls[i-1]
    num+=ls[i-1]
res/=num
if res==0:
    print(0.0)
else:
    print (str(res).split('.')[0] + '.' + str(res).split('.')[1][:1])

二.小美的代金券要过期啦
外卖节即将过去了，小美还有很代金券没有消费掉，美团面向小美这样的用户推出了一个新的活动，即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排，小美可以进行任意多次如下操作：
如果存在相邻的两个代金券金额相等,设其面额为x，小美可以使用这两张代金券换一张面额为x+1的代金券，并将其仍放在原来两张券的位置上，每进行一次这样的操作，小美就可以获得1元可以无限期使用的奖励金。
小美觉得奖励金可太香了，因此她想获得尽可能多的奖励金，请问她最多可以获得多少奖励金。

输入描述
输入第一行仅包含一个正整数n，表示小美拥有的代金券数量。(1<=n<=500)
输入第二行包含n个正整数，每个整数x表示一张代金券的面额，同时这也是系统排出的代金券顺序。(1<=x<=100)
输出描述
输出仅包含一个整数，表示小美最多可以获得的奖励金数量。

样例输入
5
1 1 1 1 1
样例输出
3

提示
样例解释：
{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}

AC

n = int(input())
ls = list(map(int,input().split()))

def xxl(nums):
    A=0
    N=len(nums)
    i=N-1
    while i>0:
        if nums[i]==nums[i-1]:
            nums.pop(i)
            nums[i-1]+=1
            A+=1
            N-=1
            i=N-1
        else:
            i-=1
    return A


if n==1:
    print(0)
else:
    print(xxl(ls))

三.小美的外卖节省钱计划
2020年的618不再仅仅是购物节啦，同时也是美团外卖节，小美早早就准备好了各种满减代金券，为了最大程度的“省钱”，当然是选择把这些代金券都用光啦！
这些代金券都有一个使用门槛，即满多少元的订单才可以使用。如果使用一个二元组<x,y>表示一张代金券，即需要满x元才能优惠y元，那么需要注意的是，并不是所有代金券的x都是大于等于y的，良心美团也会推出一些x<y的代金券。如果x<y,例如x=1，y=2，则购买1元商品的情况下无需付款，不会退款给用户。
请问小美如果想用完这些代金券，在保证总付款金额最小的情况下，她最多购买多少钱的外卖呢？
说明：
1.一个订单只能用一张代金券。
2.同时满足总付款金额最少，且购买的外卖价值最高，例如两个优惠完都是1元的外卖，一个原价3元另一个原价4元，则选四元的。
3.由于美团商户很多，所以对于任何一个价格我们都可以找到至少一种商品购买。

输入描述
输入第一行仅包含一个正整数n，表示小美拥有的代金券数量。(1<=n<=50000)
接下来有n行，每行有两个整数x和y，表示一张代金券需要订单金额满x元可以使用，能够优惠y元。(1<=x<=10000,1<=y<=10000)
输出描述
输出仅包含两个正整数，中间用空格隔开,分别表示小美购买的外卖价值和她的实际付款金额。

样例输入
3
5 3
10 5
1 2
样例输出
17 7

AC

n = int(input())
ls=[]
for _ in range(n):
    ii = list(map(int,input().split()))
    ls.append(ii)

def dj(nums):
    values=0
    actualyouhui=0
    for i in range(len(nums)):
        if nums[i][0]>=nums[i][1]:
            values+=nums[i][0]
            actualyouhui+=nums[i][1]

        else:
            values+=nums[i][1]
            actualyouhui+=nums[i][1]

    return [values,values-actualyouhui]
res=dj(ls)
print(res[0],end=" ")
print(res[1])