美团2018CodeM资格赛

发表于 |

共6道，3道AC，1道WA，2道放弃，还差的好远啊呜呜呜~

下单(AC)

美团在吃喝玩乐等很多方面都给大家提供了便利。最近又增加了一项新业务：小象生鲜。这是新零售超市，你既可以在线下超市门店选购生鲜食品，也可以在手机App上下单，最快30分钟就配送到家。
新店开张免不了大优惠。我们要在小象生鲜超市里采购n个物品，每个物品价格为ai，有一些物品可以选择八折优惠（称为特价优惠）。
有m种满减优惠方式，满减优惠方式只有在所有物品都不选择特价优惠时才能使用，且最多只可以选择最多一款。
每种满减优惠描述为(bi,ci)，即满bi减ci（当消费>=bi时优惠ci）。
求要买齐这n个物品（必须一单买齐），至少需要多少钱（保留两位小数）。

输入描述:

第一行，两个整数n,m。
接下来n行，每行一个正整数ai，以及一个0/1表示是否可以选择特价优惠（1表示可以）。
接下来m行，每行两个正整数bi,ci，描述一款满减优惠。

1 <= n,m <=10
1 <= ai <= 100
1 <= ci < bi <= 1000

输出描述:

一行一个实数，表示至少需要消耗的钱数（保留恰好两位小数）。
示例1
输入
2 1
6 1
10 1
12 2
输出
12.80
示例2
输入
2 2
6 1
10 1
5 1
16 6
输出
10.00

分析：只能说幸好把，这第一题比较简单，否则一道都做不出来是真的尴尬，要么全价买然后享受满减优惠，要么直接特价买，最后比较大小即可，取值范围都宽松，怎么写都行

思路：用一个变量totalcost记录全价,decost记录特价（8折）,然后totalcost和满减政策依次比较取最优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
while True:
    try:
        n,m = map(int,raw_input().split())
        totalcost = 0
        decost = 0
        for i in range(n):
            val,flag = map(int,raw_input().split())
            totalcost += val
            if flag == 1:
                decost += val * 0.8
            else:
                decost += val
        res = float('inf')
        for i in range(m):
            b,c = map(int,raw_input().split())
            if totalcost >= b:
                res = min(res,totalcost-c)
        print '%.2f' % min(decost,res)
    except:
        break

可乐(AC)

小美和小团最近沉迷可乐。可供TA们选择的可乐共有k种，比如可口可乐、零度可乐等等，每种可乐会带给小美和小团不同的快乐程度。
TA们一共要买n瓶可乐，每种可乐可以买无限多瓶，小美会随机挑选其中的m瓶喝，剩下的n-m瓶小团喝。
请问应该如何购买可乐，使得小美和小团得到的快乐程度的和的期望值最大？
现在请求出购买可乐的方案。

输入描述:

第一行三个整数n，m，k分别表示要买的可乐数、小美喝的可乐数以及可供选择的可乐种数。
接下来k行，每行两个整数a，b分别表示某种可乐分别给予小美和小团的快乐程度。
对于所有数据，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000
输出描述:
一行k个整数，第i个整数表示购买第i种可乐的数目。
如果有多解，请输出字典序最小的那个。
对于两个序列 a1, a2, …, ak, b1, b2, …, bk，a的字典序小于b，当且仅当存在一个位置i <= k满足：
ai < bi且对于所有的位置 j < i，aj = bj；
示例1
输入
2 1 2
1 2
3 1
输出
0 2
说明
一共有三种购买方案：

1. 买2瓶第一类可乐，小美和小团各喝一瓶，期望得到的快乐程度和为1+2=3；
2. 买1瓶第一类可乐和1瓶第二类可乐，小美和小团各有二分之一的概率喝到第一类可乐，另有二分之一的概率喝到第二类可乐，期望得到的快乐程度和为1*0.5+3*0.5+2*0.5+1*0.5=3.5；
3. 买2瓶第二类可乐，小美和小团各喝一瓶，期望得到的快乐程度和为3+1=4。

分析：
这道题要注意是算期望之和最大，对于某一瓶可乐，假若提供的快乐度分别为x,y，我们来计算这瓶可乐能提供的快乐度，首先对于小美，选择到可乐的概率为m/n，则度为m/n * x,小团则为(n-m)/n * y。即对于若干组x,y，求ax+by的最大值，其中a+b=1。
如果能想到这一步，应该就不难了，因为x,y都有确定的值，在这么多组中x,y总有一个使得ax+by最大，所以就只买这一个就可以了。

思路：
依次读取数据进行比较，注意要按照字典序最小输出,（00002 02000）则输出00002

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while True:
    try:
        n,m,k = map(int,raw_input().split())
        index,res = 0,-float('inf')
        a,b = float(m)/n,float(n-m)/n
        for i in range(k):
            x,y = map(int,raw_input().split())
            if a*x + b*y >= res: 
                index = i
                res = a*x + b*y
        ans = [0] * k
        ans[index] = n
        print ' '.join(map(str,ans))
        
    except:
        break

世界杯(AC)

世界杯就要开始啦！真真正正的战斗从淘汰赛开始，现在我们给出球队之间的胜负概率，来预测每支球队夺冠的可能性。
在接下来的篇幅中，我们将简单介绍淘汰赛阶段的规则。
淘汰赛阶段的90分钟常规时间内（含补时阶段）进球多的球队取胜，如果参赛双方在90分钟内（含补时阶段）无法决出胜负，将进行上下半场各15分钟的加时赛。加时赛阶段，如果两队仍未分出胜负，则通过点球大战决出胜者。也就是说，每场比赛，有且仅有一个队能够晋级到下一轮。
淘汰赛共有16支球队参加（小组赛阶段共分8个小组，每组前两名晋级），对阵安排如下。

1/8决赛
A组第一对阵B组第二=胜者1
B组第一对阵A组第二=胜者2
C组第一对阵D组第二=胜者3
D组第一对阵C组第二=胜者4
E组第一对阵F组第二=胜者5
F组第一对阵E组第二=胜者6
G组第一对阵H组第二=胜者7
H组第一对阵G组第二=胜者8
获胜的8个队进入1/4决赛，即所谓“8强”
1/4决赛
胜者1对阵胜者3=胜者A
胜者2对阵胜者4=胜者B
胜者5对阵胜者7=胜者C
胜者6对阵胜者8=胜者D
1/4决赛的4个获胜队进入“4强”
半决赛
胜者A对阵胜者C
胜者B对阵胜者D
半决赛获胜两队进入决赛，失利的两队争夺三名
决赛获胜的队伍就是最后的冠军！

输入描述:

球队会被以1..16进行标号，其分别表示：
1 A组第一；
2 B组第二；
3 C组第一；
4 D组第二；
5 E组第一；
6 F组第二；
7 G组第一；
8 H组第二；
9 B组第一；
10 A组第二；
11 D组第一；
12 C组第二；
13 F组第一；
14 E组第二；
15 H组第一；
16 G组第二。

数据共有16行，每行16个浮点数，第i行第j列的数Fi,j表示i和j进行比赛时i获胜（包括常规时间获胜、加时赛获胜以及点球大战获胜）的概率。
对于1 <= i, j <= 16 且 i != j, 满足0 <= Fi,j <= 1, Fi,j + Fj,i = 1；
对于1 <= i <= 16, 满足 Fi,i = 0。

输出描述:

输出一行16个浮点数，用空格隔开，分别表示每只球队获得世界杯的概率，结尾无空格。
绝对误差或相对误差在1e-5之内的解会被判为正确。

分析：
本题从思维难度上来讲不高，但就是要仔细分析，认真写出哪几个队进行比赛，求概率乘积即可

12(胜者1) 34(胜者3)·····决出胜者A
···································进入决赛
56(胜者5) 78(胜者7)·····决出胜者C
··············································最终冠军
910(胜者2) 1112(胜者4)··决出胜者B
···································进入决赛
1314(胜者6) 1516(胜者8)··决出胜者D

思路：
分别用矩阵讲每轮的概率存储,例如first存储每个队进8强的概率,second存储4强的概率,依次类推。每次计算思路一样，是可以用函数写的，比如 helper(turn,list1,list2)两个list代表i，j遍历的数据，turn表示轮数，当计算third的时候就写second，那样写代码应该会好看很多，但是我心态已经不太好了，就这样把。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
while True:
    try:
        p = [[0.0]*16 for _ in range(16)]
        for i in range(16):
            p[i] = map(float,raw_input().split())
        # 8强概率
        first = [0.0] * 16
        for i in [0,2,4,6,8,10,12,14]:
            first[i] = p[i][i+1]
            first[i+1] = p[i+1][i]
        # 4强概率
        second = [0.0] * 16
        for i in [0,4,8,12]:
            second[i] = first[i] * (first[i+2]*p[i][i+2] + first[i+3]*p[i][i+3])
            second[i+1] = first[i+1] * (first[i+2]*p[i+1][i+2] + first[i+3]*p[i+1][i+3])
        for i in [2,6,10,14]:
            second[i] = first[i] * (first[i-2]*p[i][i-2] + first[i-1]*p[i][i-1])
            second[i+1] = first[i+1] * (first[i-2]*p[i+1][i-2] + first[i-1]*p[i+1][i-1])
        # 决赛概率,写到这里才发现应该可以用函数写，龟龟，心态都蹦了
        third = [0.0] * 16
        for i in [0,1,2,3]:
            P = 0
            for j in [4,5,6,7]:
                P  += second[j]*p[i][j]
            third[i] = second[i] * P

        for i in [4,5,6,7]:
            P = 0
            for j in [0,1,2,3]:
                P  += second[j]*p[i][j]
            third[i] = second[i] * P

        for i in [8,9,10,11]:
            P = 0
            for j in [12,13,14,15]:
                P  += second[j]*p[i][j]
            third[i] = second[i] * P

        for i in [12,13,14,15]:
            P = 0
            for j in [8,9,10,11]:
                P  += second[j]*p[i][j]
            third[i] = second[i] * P
        # 夺冠
        final = [0.0] * 16
        for i in [0,1,2,3,4,5,6,7]:
            for j in [8,9,10,11,12,13,14,15]:
                final[i] += third[j]*p[i][j]
            final[i] *= third[i]

        for i in [8,9,10,11,12,13,14,15]:
            for j in [0,1,2,3,4,5,6,7]:
                final[i] += third[j]*p[i][j]
            final[i] *= third[i]

        print ' '.join(map(str,final))
            
    except:
        break

分数

小胖参加了人生中最重要的比赛——MedoC资格赛。MedoC的资格赛由m轮构成，使用常见的“加权标准分”的规则。每位选手需要参加所有的m轮的比赛。在一轮中，能取得的分数为自己的成绩除掉最高分的成绩。每个选手的总分为每一轮获得的分数乘上这一轮比赛占得比重。如果在某一轮比赛中所有人获得了零分，那么所有选手在这一轮获得的分数都为0分。
比如说，资格赛一共3轮，三轮的权重分别为30%, 30%, 40%。在第一轮中，小胖获得了300分，最高分也为300分。在第二轮中，小胖获得了0分，最高分也为0分。在第三轮中，小胖获得了150分，最高分为300分，那么小胖的总分为(300/300)*30%+0*30%+(150/300)*40%=0.5。
一共有n位选手参加了比赛，其中成绩最高的k位选手能够晋级到初赛。如果有多人在分数线上同分，那么系统会随机在这些同分的人中选取，选满k个晋级为止。
小胖现在知道了每个选手每场比赛的成绩，但是由于他的疏忽，其中的某个人某场比赛的成绩消失了。所以更多人出线的情况变得未知起来。现在只知道成绩一定是0到C之间的一个整数（包含0和C）。
小胖想知道对于每个人的出线情况是怎么样的，也就是一定能出线，一定不能出线还是有可能出线。

输入描述:

第一行四个正整数n,m,k,C (m <= 6, k <= n <= 500, C <= 500)。
接下来一行m个整数w1, w2, …, wm，表示每场比赛的权重，第i场比赛的权重为wi/(w1+w2+…+wm)，保证wi >= 0且1 <= w1 + w2 + … + wm <= 1000。
接下来n行每行m个整数，第i个整数表示这个选手在第i场比赛中获得的成绩。如果这个数字为-1表示这个数据丢失，保证恰好有一个-1。

输出描述:

n行每行输出一个1到3之间的整数。1表示一定出线，2表示一定不出线，3表示可能出线。

示例1
输入

4 2 2 100
1 1
100 99
70 70
40 -1
100 39

输出

1
3
3
2

分析：
其它分数全部固定只有这个-1会变（从0到C），不妨设本身这一轮比赛的最大分值为M
首先分数从0开始涨到M，这一过程其它人分数不变，这个人分数在上升，或许能挤掉一些人
然后分数从M开始涨到C，这一过程这个人分数不变，其他人分数在下降(对这轮分高的不利，排名可能会下降)，或许又能挤掉一些人
那么我想0，C这两个点应该是极端情况才对，应该只考虑这两种情况就行了吧，难道要考虑M的情况？
这道题还没搞懂是哪里想错了，就pass 3.7%（或许就过了测试样例吧），这里先写下两种思路吧

思路：
方法1： 假设没有这个-1，有谁可以肯定出线或者有概率出线（同分情况）是可以计算出来的，我们写一个函数来计算，返回一个列表，1代表肯定能出现，3代表有概率出线，0代表不能出线。然后我们找到这个-1，将它改成0计算一次结果，改成C计算一次结果，比较这两次结果即可。(pass 3.7%)

方法2： 先不考虑有-1的那一轮，将其他的分数全部计算，指针先指着第K个人，然后从0到C遍历，分别计算分数，但是这样感觉特别麻烦，比如 分数3 3 3 3 2，晋级4个，那么当2涨到3的时候，所有人状态全混了，代码上也没法简洁处理的样子，但是感觉这种办法肯定万无一失，毕竟全算了，而且C<500，应该也不会超时。

更新：
在网上看到别人通过的代码，思路就是把C全部考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
while True:
    try:
        n,m,k,C = map(int,raw_input().split())
        w = map(int,raw_input().split())
        S= sum(w)
        w = [float(w[i])/S for i in range(m)]

        score = [[] for _ in range(n)]
        for i in range(n):
            score[i] = map(int,raw_input().split())
        # 计算函数
        def herlper(score):
            rec = zip(*score)
            res = [0] * n
            ans = [0] * n
            for i in range(m):
                M = float(max(rec[i]))
                for j in range(n):
                    res[j] += rec[i][j]/M * w[i]
            heap = [(res[i],i) for i in range(n)]
            heap.sort(key= lambda x:x[0],reverse=True)
            # 处理同分情况
            i = 0
            while i < k:
                j = i+1
                while heap[j][0] == heap[j-1][0]:
                    j += 1
                if j > k:
                    ans[i:j] = [3] * (j-i)
                else:
                    ans[i:j] = [1] * (j-i)
                i = j
            return ans
        # 找-1修改
        for i in range(n):
            for j in range(m):
                if score[i][j] == -1:
                    score[i][j] = 0
                    res1 = herlper(score)
                    score[i][j] = C
                    res2 = herlper(score)
                    break

        for i in range(n):
            if res1[i] == res2[i] == 1:
                print 1
            elif res1[i] != res2[i]:
                print 3
            else:
                print 2
    except:
        break

你的城市

2018年第一季度，美团旅行的酒店业务以5770万的订单总量，成为行业第一名。
与此同时，美团旅行也提供机票、火车票、船票等各种服务，不断开辟新的目的旅游城市。最近新开的目的地，就包括对小A有特殊意义的偏僻小城C。
“我来到 你的城市 熟悉的那一条街。”小A哼着歌，从北京出发，要去C城。这对他非常重要，必须当天到达，虽然交通并不是非常方便。
但是，错过火车并不是一个小概率事件。为了保险起见，小A决定选择一个即使错过火车也存在补救措施的交通方案。（即假使未赶上原方案中的任何一班火车，依然可以改乘其他的车次能够在当天到达C城，但同时小A是一个乐观主义者，所以他认为改乘以后的所有车次都不会延误。）当然了，在满足上述条件的情况下，小A希望花费的钱越少越好（只考虑计划中的，不考虑发生意外时换乘带来的代价）。
城市及交通网可以看做一张n个点m条边的有向图。每个点代表一个城市（1号点代表北京，n号点代表C城）。每条边由一个五元组< x, y, c, ts, td >组成，表示存在一个车次，由ts时刻从城市x出发，在td时刻到达城市y，且花费为c元。
为了简化问题，ts，td均为以半小时为基本单位（具体格式见样例及Hint）。并假设每次中转最少需要花费半个小时，且中转只能发生在同一城市（即到达一个城市距离再次从这个城市出发至少需要间隔半个小时），注意，小 A 如果因为没赶上车次需要改乘，也需要半个小时的时间。
问小A到达C城最少需要花费多少钱（行程必须在这一天内完成，可以在0:00上车，也可以在24:00到达）。

输入描述:

第一行，两个正整数n, m。n表示城市数量，m表示当天不同班次的火车数量。
接下来m行，每行3个整数x, y, c加两个字符串ts, td，均以空格作为分隔，表示当天的某一班火车。其中x, y, c, ts, td的含义如前描述。
所有的车次都是当天的，没有隔夜的票。
2 <= n <= 500, m <= 15000, c <= 1000, ts < td，所有数均为正整数。
车次保证不过夜，时间范围0:00, 0:30, 1:00, … , 23:00, 23:30, 24:00，可能存在重复车次。

输出描述:

一个整数，表示存在补救措施的前提下，小A到达C城的最小花费。如果不存在这样的路径，则输出-1。
示例1
输入
3 5
1 3 800 18:00 21:00
1 2 650 13:30 14:00
2 3 100 14:00 18:00
2 3 300 14:30 19:00
2 3 200 15:00 19:30
输出
950
说明
选择第二个和第四个车次。
第三个车次由于中转时间太短无法选择。第五个车次由于没有可改乘的航班无法选择。
如果错过第二个车次，可以改乘第一个车次。如果错过第四个车次，可以改乘第五个车次。
示例2
输入
3 5
1 2 1000 0:00 12:00
1 2 100 0:30 14:00
1 2 100 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
输出
1300
说明
选择第一个和第四个车次。
不能选择第二个车次是因为，如果错过了0:30的车次2，那么同样在0:30出发的车次3也是来不及改乘的。
示例3
输入
3 4
1 2 100 0:30 14:00
1 2 200 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
输出
-1
说明
和样例二类似，但是缺少了原先的车次一，所以没有换乘方案。
示例4
输入
3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
输出
400
说明
选择第一个和第三个车次。
示例5
输入
3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:30
2 3 300 16:00 24:00
2 3 200 16:30 24:00
输出
-1
说明
和样例四类似，但假如错过了第一个车次，改乘车次二在16:30到达城市2是不足以赶上16:30出发的车次四的。

匹配

美团外卖日订单已经超过2000万，背后有一个非常复杂的智能调度系统。
我们考虑一个简化的情形，有n个外卖小哥要去 n 家商店取货，第 i 个外卖小哥到达商店 j 需要时间 e[i][j] 。现在有 m 对外卖小哥和商店的合作关系。假定每个外卖小哥只能取到一个货物，每个商店只需要一位外卖小哥取货。
询问最少多少时间，能有 k 位外卖小哥到达 k 个商店取到货物？对于每个 k ，都输出一个数表示最少使用时间，如果无解输出 -1。

输入描述:

第一行输入两个整数 n , m （1 <= n <= 1000 , 1 <= m <= 100000）。
接下来 m 行，每行输入 3 个整数 i , j , e[i][j] (1 <= i, j <= n , 0 <= e[i][j] <= 10^9)，定义如题所述。
注：本题测试用例较多，请耐心等待判题结果，也可以去排行榜刷新查看自己的提交结果。

输出描述:

输出一行n个整数，第 i 个整数，表示当 k=i 时，需要的最少时间，如果无解输出-1，结尾无空格。
示例1
输入
3 7
1 3 5
2 3 2
3 1 7
1 2 0
2 3 2
3 2 0
2 1 5
输出
0 2 5