链接：

题意：有n双手袜（1<=n<=5000），每双袜子都有颜色ci（1<=c<=100），现在重新分配，问可否使每双袜子左右手颜色不同。若可以，输出一种方案；若不可以，求maximum，同样也输出一种maximum的方案。

输出格式：

第一行是n或maximum

以下每行有两个数表示手袜颜色，一个是左手的，一个是右手的 

 

思路：先求每种颜色有几双，设最大的是maxc双

若maxc>n/2，则不能令所有袜子所有手颜色不同。输出方案是，maxc的颜色选一个，其他颜色选一个，组成一双。注意一双手袜拆分成一个左手手袜，一个右手手袜，位置不一样。

最后剩余的是maxc颜色的袜子，直接输出。

若maxc<=n/2，则存在方案是每双手袜的颜色不一样。方案很多，只要保证每双手袜颜色都不同即可。

我的方法，先按颜色排序，然后首尾交换，遇到中间可能存在左右颜色一样的，就更前面已匹配的交换。

也可以先按颜色排序，然后将数组截成两份，两个数组匹配。手袜为奇数对时，有一双需要特殊处理。

 1 #include <iostream>

 2 #include <cstring>

 3 

using 

namespace std;

 4 

 5 

const 

int N = 

5005;

 6 

const 

int M = 

105;

 7 

 8 

int main()

 9 {

10     

int n, m, a[M], c, maxc, ans[

2*N], indexa, finalAns[

2*N];

11     cin >> n >> m;

12     memset(a, 

0, 

sizeof(a));

13     maxc = 

0;

14     

for(

int i=

1; i<=n; i++)

15     {

16         cin >> c;

17         a[c] += 

2;

18         

if(a[maxc]<a[c]) maxc = c;

19     }

20     

if(a[maxc] > n)

21     {

22         

int flag = 

1;

23         cout << (n - a[maxc]/

2)*

2 << endl;

24         

for(

int i=

1; i<=m; i++)

25         {

26             

if(maxc==i) 

continue;

27             

while(a[i]>

0)

28             {

29                 

if(flag%

2==

1)

30                     cout << maxc << 

"

 

" << i << endl;

31                 

else

32                     cout << i << 

"

 

" << maxc << endl;

33                 flag++;

34                 a[i]--;

35             }

36         }

37         

for(

int i=

1; i<=n - (n - a[maxc]/

2)*

2; i++)

38             cout << maxc << 

"

 

" << maxc << endl;

39     }

40     

else

41     {

42         cout << n << endl;

43         indexa = 

0;

44         

for(

int i=

1; i<=m; i++)

45         {

46             

while(a[i]>

0)

47             {

48                 ans[++indexa] = i;

49                 a[i]--;

50             }

51         }

52         

int flag = 

1, indexfinal = 

0;

53         

int l = 

1, r = indexa;

54         

while(l<r)

55         {

56             

if(flag%

2==

1)

57             {

58                 finalAns[l*

2-

2] = ans[l];

59                 finalAns[l*

2-

1] = ans[r];

60                 

if(finalAns[l*

2-

2]==finalAns[l*

2-

1])

61                 {

62                     swap(finalAns[l*

2-

2],finalAns[indexfinal]);

63                     indexfinal += 

2;

64                 }

65                 l++; r--;

66             }

67             

else

68             {

69                 finalAns[l*

2-

2] = ans[r];

70                 finalAns[l*

2-

1] = ans[l];

71                 

if(finalAns[l*

2-

2]==finalAns[l*

2-

1])

72                 {

73                     swap(finalAns[l*

2-

2],finalAns[indexfinal]);

74                     indexfinal += 

2;

75                 }

76                 l++; r--;

77             }

78             flag++;

79         }

80         

for(

int i=

0; i<indexa/

2; i++)

81             cout << finalAns[

2*i] << 

"

 

" << finalAns[

2*i+

1] << endl;

82     }

83     

return 

0;

84 }

 

 --------------------------------------

理解题意是王道。