Q:
简易题面:
给n个三元集,包含 1 到 n ,-1 到 -n,和 n 个 0,每次交换两个集合中的一对元素,求最少交换几次可以使每个集合中恰好包含一对相反数与 0。
标准一点的题面(?):
给 n 个三元集合,1 到 n (包含)中的每个整数在 n 个集合中恰好出现一次,-n 到 -1 中的每个整数在 n 个集合中恰好出现一次,此外 0 在 n 个集合中恰好出现 n 次,例如:
n=3
S1: 1,2,0
S2: -1,0,0
S3: 3,-3,-2
定义一次操作为选定两个集合 Sa,Sb ,从 Sa 中取出一个元素并加入 Sb,同时从 Sb 中取出一个元素加入 Sa 。(交换两个集合中的两个元素)。
定义一个三元集为好,当且仅当其中包含一个 0 ,一个正整数,一个负整数,且正整数是负整数的相反数( S={k,-k,0} )。
求使 n 个三元集均为好的最小操作次数。