hdu--6168--Numbers

Love The Way You Lie 2022-06-09 00:13 183阅读 0赞

# Numbers #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)  
Total Submission(s): 162    Accepted Submission(s): 86**

Problem Description

zk has n numbers  a1,a2,...,an. For each (i,j) satisfying 1≤i<j≤n, zk generates a new number  (ai\+aj). These new numbers could make up a new sequence  b1，b2,...,bn(n−1)/2. 
LsF wants to make some trouble. While zk is sleeping, Lsf mixed up sequence a and b with random order so that zk can't figure out which numbers were in a or b. "I'm angry!", says zk. 
Can you help zk find out which n numbers were originally in a?

Input

Multiple test cases(not exceed 10).  
For each test case:  
 ∙The first line is an integer m(0≤m≤125250), indicating the total length of a and b. It's guaranteed m can be formed as n(n+1)/2.  
 ∙The second line contains m numbers, indicating the mixed sequence of a and b.  
Each   ai is in \[1,10^9\]

Output

For each test case, output two lines.  
The first line is an integer n, indicating the length of sequence a;  
The second line should contain n space-seprated integers   a1,a2,...,an(a1≤a2≤...≤an). These are numbers in sequence a.  
It's guaranteed that there is only one solution for each case.

Sample Input

6
    2 2 2 4 4 4
    21
    1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 8 8 9 9 10 11

Sample Output

3
    2 2 2
    6
    1 2 3 4 5 6

题意：

有n个数的序列a（a1......an），可以两两组合成n（n-1）／2个数的b序列。把它们混成一个数组，让你求出原n个数的a序列。

解题思路：

因为b序列是由两个a序列的元素组合而成，所以 混合的这个序列按从小到大排序后，前两个较小的数一定为a序列中的元素。假设为z\[1\],z\[2\],那么z\[1\]+z\[2\]就一定存在于b数组中。把z\[1\]+z\[2\]用map“标记”一下，继续从z\[3\]遍历混合的数组，判断z\[3\]有没有被“标记”，如果有 说明这个数为b序列中的数，跳过 继续遍历下一个。如果没有，该数就为a数组中的元素。以此类推.........

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 const&nbsp; 
 int&nbsp;N&nbsp;=&nbsp; 
 125250&nbsp;+&nbsp; 
 8; 
 map&lt; 
 int,&nbsp; 
 int&gt;&nbsp;m; 
 
 int&nbsp;a[N],&nbsp;z[N]; 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n,&nbsp;k; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(~scanf( 
 "%d",&nbsp;&amp;n)) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m.clear(); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;z[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(z&nbsp;+&nbsp; 
 1,&nbsp;z&nbsp;+&nbsp; 
 1&nbsp;+&nbsp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[k++]&nbsp;=&nbsp;z[ 
 1]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[k++]&nbsp;=&nbsp;z[ 
 2]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m[z[ 
 1]&nbsp;+&nbsp;z[ 
 2]]++;&nbsp; 
 ///表示b数组中包含该数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 3;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(m[z[i]]&nbsp;&gt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///如果b数组中有这个数， &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m[z[i]]--; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 continue; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[k++]&nbsp;=&nbsp;z[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 0;&nbsp;j&nbsp;&lt;&nbsp;k&nbsp;-&nbsp; 
 1;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m[a[j]&nbsp;+&nbsp;z[i]]++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(a,&nbsp;a&nbsp;+&nbsp;k); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;k); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "&nbsp;"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d",&nbsp;a[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>