首页 > 代码库 > Kostya the Sculptor

Kostya the Sculptor

2024-08-20 16:24:22   225人阅读

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


联系
我们