题解 | #猴子选大王#

跳转题目1

跳转题目2

一、题意简述

有 只猴子，给出 对关系 ，表示这两只猴子同时出现过一次。

定义：

• 猴子 的热度 ：它出现在多少对中
• 选择两只猴子 ，价值为：

其中 表示 同时出现的次数。

求最大价值。

二、核心思路

统计信息

• like[i]：每只猴子的热度
• both[(i,j)]：任意两只猴子共同出现的次数（双向存）

按热度分类

• mx1：最大热度
• maxs：所有热度等于 mx1 的猴子
• mx2：次大热度
• cmaxs：所有热度等于 mx2 的猴子

三、最大猴子 ≥ 2 的处理（难点）

设最大猴子数量为

if k > len(both)//2:
    print(mx1*2)
    exit()

含义是： 因为两只大猴子的情况只能是k种（组合）当k大于len(both)//2时，说明一定某个不相交，也就是both为0，可以直接输出，因此下面两重for循环不会超时

4️⃣ 否则正常枚举

res = max(
    like[a] + like[b] - both[(a,b)]
    for a,b in maxs pairs
)

四、最大猴子 = 1 的情况

只能选：

• 1 只最大猴子
• 1 只次大猴子

枚举所有 (maxs[0], cmaxs[i]) 即可。

五、完整 Python 实现（你的 AC 版本）

import sys
from collections import defaultdict
from collections import Counter
input=sys.stdin.readline

def solve():
    n,m=map(int,input().split())
    like=[0]*(m+1)
    both=defaultdict(int)
    for _ in range(n):
        a,b=map(int,input().split())
        #if a>b:a,b=b,a
        like[a]+=1
        like[b]+=1
        both[(a,b)]+=1
        both[(b,a)]+=1
    cnt=Counter(like[1:])
    cnt=[k for k in cnt.keys()]
    cnt.sort(reverse=True)

    mx1=cnt[0]
    maxs=[i for i in range(m+1) if like[i]==mx1]
    if len(maxs)==2:
        res=like[maxs[1]]+like[maxs[0]]-both[(maxs[0],maxs[1])]
        print(res)
        return 
    N=len(maxs)
    if len(maxs)>=2:
        k=N*(N-1)//2 #不是很好理解，一个优化
        if k>len(both)//2:
            print(mx1*2)#肯定有一种组合不在both中，也不在小猴子选举中，所以both返回0
            exit()
        res=0
        for i in range(len(maxs)):
            for j in range(i+1,len(maxs)):
                res=max(res,like[maxs[i]]+like[maxs[j]]-both[(maxs[i],maxs[j])])
        print(res)
        return
    if len(cnt)>=2:
        mx2=cnt[1]
    if len(maxs)==1:
        res=0
        cmaxs=[i for i in range(m+1) if like[i]==mx2]
        for i in range(len(cmaxs)):
            res=max(res,like[maxs[0]]+like[cmaxs[i]]-both[(maxs[0],cmaxs[i])])
        print(res)
        return
for _ in range(1):
    solve()