Codeforces Global Round 14 D. Phoenix and Socks(贪心/好题)

To satisfy his love of matching socks, Phoenix has brought his n socks (n is even) to the sock store. Each of his socks has a color ci and is either a left sock or right sock.

Phoenix can pay one dollar to the sock store to either:

  • recolor a sock to any color c′ (1≤c′≤n)
  • turn a left sock into a right sock
  • turn a right sock into a left sock

The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa.

A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make n/2 matching pairs? Each sock must be included in exactly one matching pair.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains three integers n, l, and r (2≤n≤2⋅10^5; n is even; 0≤l,r≤n;l+r=n) — the total number of socks, and the number of left and right socks, respectively.

The next line contains

上一篇:吉林长春东北师范大学附属中学集训游记


下一篇:snap设置代理