poj1018Communication System
题意：有n个devices，每个devices有mi条网线与别的devices相连，每条网线有带宽b和价格p两个属性。（第一个device到最后一个device之间的）通路的总带宽为通路上带宽最小的那条网线的带宽，通路的价格为通路上所有网线的价格之和。求所有通路中最大的那个minb/sump。
错误的解题思路：
回溯。用回溯是万万不行的，数据量是100^100。
正确的解题方式：
枚举所有的带宽b，即将所有出现的带宽指定为minb枚举一遍，对每个device，只需要选出device_b >= minb && device_p尽可能小。求出性价比最高的那个。数据量100 * 100。
如果对某一个device，它的网线没有一条b >= minb，直接跳过本轮即可，因为这条通路的性价比不可能是最大的（任意选一个这个device的b代替minb即可得到一个更大的性价比）。
反思：自己对数字不是很敏感，看到处理数字的题，就感觉很抽象，无从下手。
代码

posted on 2013-03-27 17:53 小鼠标 阅读(179) 评论(0)  编辑 收藏 引用 所属分类: Java基础练习

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2013年3月>
日一二三四五六
242526272812
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的，所以在OJ有时候“卡住”了也不要太灰心，没准真的不是自己的原因呢。
    加油，祝你好运啦！
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说，Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: （转）ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。？
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主，谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况，书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜