To solve this problem, we need to determine the maximum number of people that can be seated around a circular table such that no two people from the same group are adjacent.

Approach

The key insight to solve this problem is based on the following observations:

1. Let the size of the largest group be max_group and the sum of the sizes of all other groups be sum_rest.
2. If the size of the largest group (max_group) is less than or equal to the sum of the sizes of the other groups (sum_rest), then all people can be seated around the circular table. This is because we can place each member of the largest group between members of other groups.
3. If the size of the largest group exceeds the sum of the sizes of the other groups, then the maximum number of people that can be seated is 2 * sum_rest. This is because each member of the other groups can separate at most two members of the largest group (and since it's a circular arrangement, we can't have more than sum_rest members of the largest group to avoid adjacency).

Solution Code

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N = int(input[ptr])
        ptr +=1
        groups = list(map(int, input[ptr:ptr+N]))
        ptr += N
        max_g = max(groups)
        sum_g = sum(groups)
        sum_rest = sum_g - max_g
        if max_g <= sum_rest:
            print(sum_g)
        else:
            print(sum_rest * 2)

if __name__ == "__main__":
    main()

Explanation

1. Reading Input: The input is read all at once for efficiency, especially for multiple test cases.
2. Processing Each Test Case: For each test case:
   • We read the number of groups N and the list of group sizes.
   • Calculate the size of the largest group (max_g) and the sum of all group sizes (sum_g).
   • Compute sum_rest as the sum of all groups except the largest one.
   • Apply the conditions to determine the maximum number of people that can be seated:
     • If max_g ≤ sum_rest, all people can be seated (output sum_g).
     • Otherwise, output 2 * sum_rest as the maximum number of people that can be seated without adjacency issues.

This approach efficiently handles all edge cases (like a single group, equal group sizes, etc.) and runs in linear time relative to the number of groups, making it optimal for the problem constraints.

作者声明:本文包含人工智能生成内容。