这恰恰证明了版主说的那句话的重点: 无知
版主是前辈风范, 不好意思把话说太白了. 你真不明白?

看过版主的代码，稍NB，没个几年估计不行。c_printf也不要太在意了，初衷都是帮忙的，没必要搞得很难堪，大家还是好朋友，点到为止。

Huzi酱是个非常贪玩的人，除了魔方他还喜欢各种各样的玩具，所以他的"吕鹏友"为了哄他高兴，每次都要带上新的玩具去见他，这次"吕鹏友"带来的玩具是俄罗斯套娃，就是一种来自俄罗斯的
很出名的玩具，外面看上去有点像不倒翁，里面是空的，不同的套娃体积不同，因此大的套娃可以套住小的套娃。Huzi酱发现"吕鹏友"送给他的俄罗斯套娃有些特别：

1.体积较大的套娃能套住体积较小的套娃，但是体积一定要3倍以上。例如A套娃的体积是3，B套娃的体积是1，那么A可以套住B；A套娃的体积是10，B套娃的体积是3，A的体积是B的3.3333倍，
是3倍以上，所以也能套住。

2.一个大的套娃只能套住一个小的套娃。例如有A,B,C，3个套娃，体积分别为1，2,10。那么C套娃只能套住A或B其中一个，不能同时套住

3.如果一个套娃被另一个大的套娃套住了，那么它不能再套另一个小的套娃。例如A,B,C，3个套娃体积分别为1,3,9，C可以套住B，但是B已经被C套住了，所以B不能再套A（虽然在体积上，B是
允许套住A的）

正在此时，Huzi酱收到了中奖短信，他被抽中了【威尼斯豪华情侣5日游】，所以Huzi酱决定带上他的俄罗斯套娃和"吕鹏友"一起去旅游，但套娃的数量实在太多了，占用了行李箱太多空间，所以
Huzi酱希望用大的套娃套住小的套娃，以便减少俄罗斯套娃的个数，方便携带。但Huzi酱一直不知道要怎么计算出，他能携带的最少的套娃数量，请他帮帮他吧



输入格式
多组测试数据(1<=T<=20)，以EOF结束
每组测试数据格式如下：
第1行，一个数字n，1<=n<=500,表示俄罗斯套娃的数量
第2行，n个正整数,第k个正整数a[k]表示第k个套娃的体积，1<=a[k]<=500


输出格式
每组测试数据输出一个正整数，表示经过嵌套后，剩下的俄罗斯套娃的个数


输入样例
6
9 1 3 27 243 81
5
2 3 1 3 1
6
3 3 1 1 3 1


输出样例
3
3
3


Hint
输入以EOF结束：
n:套娃数量

int main(){
      while(scanf("%d",&n)!=EOF){
            ..............
      }
      return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~不好意思~~最近忙，就没上网，没想到这让你们那么纠结~~现在发给你们原题

Huzi酱是个非常贪玩的人，除了魔方他还喜欢各种各样的玩具，所以他的"吕鹏友"为了哄他高兴，每次都要带上新的玩具去见他，这次"吕鹏友"带来的玩具是俄罗斯套娃，就是一种来自俄罗斯的
很出名的玩具，外面看上去有点像不倒翁，里面是空的，不同的套娃体积不同，因此大的套娃可以套住小的套娃。Huzi酱发现"吕鹏友"送给他的俄罗斯套娃有些特别：

1.体积较大的套娃能套住体积较小的套娃，但是体积一定要3倍以上。例如A套娃的体积是3，B套娃的体积是1，那么A可以套住B；A套娃的体积是10，B套娃的体积是3，A的体积是B的3.3333倍，
是3倍以上，所以也能套住。

2.一个大的套娃只能套住一个小的套娃。例如有A,B,C，3个套娃，体积分别为1，2,10。那么C套娃只能套住A或B其中一个，不能同时套住

3.如果一个套娃被另一个大的套娃套住了，那么它不能再套另一个小的套娃。例如A,B,C，3个套娃体积分别为1,3,9，C可以套住B，但是B已经被C套住了，所以B不能再套A（虽然在体积上，B是
允许套住A的）

正在此时，Huzi酱收到了中奖短信，他被抽中了【威尼斯豪华情侣5日游】，所以Huzi酱决定带上他的俄罗斯套娃和"吕鹏友"一起去旅游，但套娃的数量实在太多了，占用了行李箱太多空间，所以
Huzi酱希望用大的套娃套住小的套娃，以便减少俄罗斯套娃的个数，方便携带。但Huzi酱一直不知道要怎么计算出，他能携带的最少的套娃数量，请他帮帮他吧



输入格式
多组测试数据(1<=T<=20)，以EOF结束
每组测试数据格式如下：
第1行，一个数字n，1<=n<=500,表示俄罗斯套娃的数量
第2行，n个正整数,第k个正整数a[k]表示第k个套娃的体积，1<=a[k]<=500


输出格式
每组测试数据输出一个正整数，表示经过嵌套后，剩下的俄罗斯套娃的个数


输入样例
6
9 1 3 27 243 81
5
2 3 1 3 1
6
3 3 1 1 3 1


输出样例
3
3
3


Hint
输入以EOF结束：
n:套娃数量

int main(){
      while(scanf("%d",&n)!=EOF){
            ..............
      }
      return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~不好意思~~最近忙，就没上网，没想到这让你们那么纠结~~现在发给你们原题

Huzi酱是个非常贪玩的人，除了魔方他还喜欢各种各样的玩具，所以他的"吕鹏友"为了哄他高兴，每次都要带上新的玩具去见他，这次"吕鹏友"带来的玩具是俄罗斯套娃，就是一种来自俄罗斯的
 很出名的玩具，外面看上去有点像不倒翁，里面是空的，不同的套娃体积不同，因此大的套娃可以套住小的套娃。Huzi酱发现"吕鹏友"送给他的俄罗斯套娃有些特别：

1.体积较大的套娃能套住体积较小的套娃，但是体积一定要3倍以上。例如A套娃的体积是3，B套娃的体积是1，那么A可以套住B；A套娃的体积是10，B套娃的体积是3，A的体积是B的3.3333倍，
 是3倍以上，所以也能套住。

2.一个大的套娃只能套住一个小的套娃。例如有A,B,C，3个套娃，体积分别为1，2,10。那么C套娃只能套住A或B其中一个，不能同时套住

3.如果一个套娃被另一个大的套娃套住了，那么它不能再套另一个小的套娃。例如A,B,C，3个套娃体积分别为1,3,9，C可以套住B，但是B已经被C套住了，所以B不能再套A（虽然在体积上，B是
 允许套住A的）

 正在此时，Huzi酱收到了中奖短信，他被抽中了【威尼斯豪华情侣5日游】，所以Huzi酱决定带上他的俄罗斯套娃和"吕鹏友"一起去旅游，但套娃的数量实在太多了，占用了行李箱太多空间，所以
Huzi酱希望用大的套娃套住小的套娃，以便减少俄罗斯套娃的个数，方便携带。但Huzi酱一直不知道要怎么计算出，他能携带的最少的套娃数量，请他帮帮他吧



 输入格式
 多组测试数据(1<=T<=20)，以EOF结束
 每组测试数据格式如下：
 第1行，一个数字n，1<=n<=500,表示俄罗斯套娃的数量
 第2行，n个正整数,第k个正整数a[k]表示第k个套娃的体积，1<=a[k]<=500


输出格式
 每组测试数据输出一个正整数，表示经过嵌套后，剩下的俄罗斯套娃的个数


 输入样例
6
 9 1 3 27 243 81
 5
 2 3 1 3 1
 6
 3 3 1 1 3 1


输出样例
3
 3
 3


 Hint
输入以EOF结束：
n:套娃数量

int main(){
       while(scanf("%d",&n)!=EOF){
             ..............
       }
       return 0;
 }
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~不好意思~~最近忙，就没上网，没想到这让你们那么纠结~~现在发给你们原题

Huzi酱是个非常贪玩的人，除了魔方他还喜欢各种各样的玩具，所以他的"吕鹏友"为了哄他高兴，每次都要带上新的玩具去见他，这次"吕鹏友"带来的玩具是俄罗斯套娃，就是一种来自俄罗斯的
 很出名的玩具，外面看上去有点像不倒翁，里面是空的，不同的套娃体积不同，因此大的套娃可以套住小的套娃。Huzi酱发现"吕鹏友"送给他的俄罗斯套娃有些特别：

1.体积较大的套娃能套住体积较小的套娃，但是体积一定要3倍以上。例如A套娃的体积是3，B套娃的体积是1，那么A可以套住B；A套娃的体积是10，B套娃的体积是3，A的体积是B的3.3333倍，
 是3倍以上，所以也能套住。

2.一个大的套娃只能套住一个小的套娃。例如有A,B,C，3个套娃，体积分别为1，2,10。那么C套娃只能套住A或B其中一个，不能同时套住

3.如果一个套娃被另一个大的套娃套住了，那么它不能再套另一个小的套娃。例如A,B,C，3个套娃体积分别为1,3,9，C可以套住B，但是B已经被C套住了，所以B不能再套A（虽然在体积上，B是
 允许套住A的）

 正在此时，Huzi酱收到了中奖短信，他被抽中了【威尼斯豪华情侣5日游】，所以Huzi酱决定带上他的俄罗斯套娃和"吕鹏友"一起去旅游，但套娃的数量实在太多了，占用了行李箱太多空间，所以
Huzi酱希望用大的套娃套住小的套娃，以便减少俄罗斯套娃的个数，方便携带。但Huzi酱一直不知道要怎么计算出，他能携带的最少的套娃数量，请他帮帮他吧



 输入格式
 多组测试数据(1<=T<=20)，以EOF结束
 每组测试数据格式如下：
 第1行，一个数字n，1<=n<=500,表示俄罗斯套娃的数量
 第2行，n个正整数,第k个正整数a[k]表示第k个套娃的体积，1<=a[k]<=500


输出格式
 每组测试数据输出一个正整数，表示经过嵌套后，剩下的俄罗斯套娃的个数


 输入样例
6
 9 1 3 27 243 81
 5
 2 3 1 3 1
 6
 3 3 1 1 3 1


输出样例
3
 3
 3


 Hint
输入以EOF结束：
n:套娃数量

int main(){
       while(scanf("%d",&n)!=EOF){
             ..............
       }
       return 0;
 }
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~不好意思~~最近忙，就没上网，没想到这让你们那么纠结~~现在发给你们原题

排序  然后头尾用掉 不就行了吗

版主，貌似这问题真没你想得那么复杂
虽然最大匹配是对的，也可以解
不过这个图比较特殊，所以会有特殊的解法
从数学的角度分析
先排序
我考虑了一下，会有两种情况是最优的
一种是让所有没有配对的聚集在一起，但是实现起来挺难的，时间复杂度也不好
另一种就是比较简单的解法了但是是等效的
把他们对半分成两组
例如编号为（也就是下标之类的） 1 2 3 4 5 6 7 8
分成1 2 3 4  和  5 6 7 8
那么8和4 配对 如果不能配对  那么往前移动  和3 配对一直到配对完成
怎么证明是最优呢
可以把没有匹配的分成两部分，就是分半的时候两边剩下的
那么就成这种情况
n个匹配了的  m个未匹配 m个未匹配 n个匹配
假设存在最优匹配
是左边匹配左边，右边匹配右边  
那么 可以替换成  左匹配右
如果只是存在左匹配左或右匹配右，那么这样做并不会增加什么

收到的鲜花

• beyondyf 于 2014-01-21 12:06 送鲜花  50朵   附言：我很赞同

嗯，非常好的思路。我想我是受经典算法的思维局限了，感谢指正！希望以后多参与讨论，也好拓展我的思维

非常好！