序列专一
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 17 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小Z是一个专一的人，他希望能把一个序列里面的数也能够唯一(即元素之间各不相同)。因为序列刚开始可能会有重复的数，所以他需要进行一些操作。每次操作可从序列中取出两个数x,y，把max(x+y-1,max(x,y)-min(x,y)+2)放入序列中，再把x和y其中一个放入序列，丢弃另外一个。问至少需要操作多少次可以使序列里面的数各不相同。
Input
输入一个T，代表数据的组数。（T<=10）
每组数据包含一个N，代表这个序列有多少个数。（N<=100,000）
接下来一行包括N个数，分别表示序列中每个数的值x (1<=x<=100,000)。
每组数据包含一个N，代表这个序列有多少个数。（N<=100,000）
接下来一行包括N个数，分别表示序列中每个数的值x (1<=x<=100,000)。
Output
对于每个测试样例，输出一行，包含一个整数，代表至少需要操作多少次可以使序列里面的数各不相同。每个测试样例占一行。
Sample Input
3 5 1 2 3 4 5 6 2 2 3 3 4 5 4 2 2 2 2
Sample Output
0 2 3 Hint: 数据输入量较大，建议使用scanf，不要使用cin 第一组样例不需要操作。 第二组样例需要进行二次操作。第一次操作取出数2和5,丢弃2,放入5和6。第二次操作取出数3和5,丢弃3,放入5和7。最终的序列为2,3,4,5,6,7。 也可以这样对第二组样例进行操作。第一次操作取出数2和5,丢弃2,放入5和6。第二次操作取出数3和6,丢弃3,放入6和8。最终的序列为2,3,4,5,7,8。
Source
642超哥