首页 > 代码库 > Kostya the Sculptor
Kostya the Sculptor
Kostya the Sculptor
题目链接:http://codeforces.com/problemset/problem/733/D
贪心
以次小边为第一关键字,最大边为第二关键字,最小边为第三关键字排序,每次只需要找次小边和最大边均相同,最小边最大的两项即可。
因为用Python遇到很多问题,切片操作a[i:j]是左闭右开区间[i,j)
代码如下:
1 n = int(input()) 2 a = [] 3 ans,u,v = 0,-1,-1 4 for i in range(n): 5 t = [int(x) for x in input().split()] 6 t.sort() 7 if ans < t[0]: 8 ans = t[0] 9 u = v = i 10 t.append(i) 11 a.append(t) 12 13 from operator import itemgetter 14 a.sort(key=itemgetter(1,2,0),reverse=True) 15 16 i = 0 17 while i+1 < n: 18 if a[i][1:3]==a[i+1][1:3]: 19 t = min(a[i][0]+a[i+1][0],a[i][1]) 20 if ans < t: 21 ans = t 22 u = a[i][3] 23 v = a[i+1][3] 24 i += 1 25 while (i==0 or a[i][1:3]==a[i-1][1:3]) and i+1<len(a): 26 i += 1 27 28 if u == v: 29 print(1) 30 print(u+1) 31 else: 32 print(2) 33 print(u+1,v+1)
Kostya the Sculptor
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。