Codeforces Round #446 (Div. 2)

A. Greed

题意

问能否把所有可乐倒到两个罐子里

题解

挑两个最大的罐子

1 sum = 0 2 b = [] 3 n = int(input()) 4 line1 = input().split() 5 line2 = input().split() 6 for i in range(n): 7 sum += int(line1[i]) 8 b.append(int(line2[i])) 9 continue 10 b.sort() 11 cap = b[n-1] + b[n-2] 12 if sum > cap: 13 print('NO') 14 else: 15 print('YES') View Code

B. Wrath

题意

每个人手里都有一根长度为L[i]的EX咖喱棒, 只要铃声一响, 就把自己前面L[i]个人砍死(同时), 问最后活下来多少人

题解

把自己能砍死的最远的人标记+1, 自己标记-1,  扫一遍标记数组, 是正数就是死人, 0就是活人

1 n = int(input()) 2 shit = [0 for i in range(n + 1)] 3 line = input().split() 4 for i in range(n): 5 claw = int(line[i]) 6 shit[i] -= 1 7 pre = i - claw 8 if pre < 0: 9 pre = 0 10 shit[pre] += 1 11 continue 12 ans = n 13 tmp = 0 14 for i in range(n): 15 tmp += shit[i] 16 if tmp > 0: 17 ans -= 1 18 continue 19 print(ans) View Code

C. Pride

题意

给定一个数组a, 有一种操作可以把相邻的两个数(x, y)中的一个(x或者y)替换为gcd(x, y), 问全部替换成1的最少操作, 不可能时输出'-1'

题解

数组a内有1的时候, 显然答案是非1的个数

否则, 只要找到最快生成一个1的操作次数

从a[i]开始, 计算a[i]到a[j]的gcd, (i < j < n), 当区间gcd为1时, 更新最小操作数为区间的长度, 即j - i + 1

1 import math 2 n = int(input()) 3 a = [] 4 k = 0 5 line = input().split() 6 for i in range(n): 7 a.append(int(line[i])) 8 if a[i] != 1: 9 k += 1 10 continue 11 ans = n 12 for i in range(n): 13 temp = a[i] 14 cur = 0 15 for j in range(i + 1, n): 16 cur += 1 17 temp = math.gcd(temp, a[j]) 18 if temp == 1: 19 if ans > cur: 20 ans = cur 21 pass 22 pass 23 continue 24 continue 25 if k == 0: 26 print('0') 27 elif ans == n: 28 print('-1') 29 else: 30 print(ans + k - 1) View Code

D. Gluttony

1 n = int(input()) 2 a = [int(i) for i in input().split()] 3 if n == 1: 4 print(a[0]) 5 else: 6 a_with_index = [[a[i], i] for i in range(n)] 7 a_with_index.sort() 8 ans = [0 for i in range(n)] 9 for i in range(n): 10 ans[a_with_index[i][1]] = str(a_with_index[(i + 1) % n][0]) 11 print(" ".join(ans)) View Code

E. 

转载于:https://www.cnblogs.com/hexsix/p/7855957.html