第二题怎么做？【百度之星吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
第二题怎么做？收藏
贪心，先copy只有一个备份的文件。
所有都有俩备份了呢？
继续贪心，然后就没法证明正确性了
那copy到哪？ copy的目的地不同，结果也会有可能不同
可以用网络流。可惜带指针的我不会写。。。
网路流 + 二分过的。。。 可能超时。。。
类似最大流，找增广路径？？
随机化贪心重复100遍啊100遍。。
你把这道题和去年的复赛题弄混了吧。仔细读题，别想多了。另外看看这题的答疑贴。
这招牛，我怎么就没想到呢。我用了个规则比较复杂的贪心，但是两个参数都相等时居然没有随机。
同没想到。。。
我表示在10.10分的时候做出来了，我靠。。。。。第一题弄了1个半小时弄不出来...
求建模方式
我也用的网络流。。我自己数据太弱了。。怀疑可能没有随机化贪心过的多
先建立文件索引w [100000]，然后创建用来保存每台机器用时N [10000]输入获取最大文件索引 max对从 w [0 ~ max] 找到文件只有 1 个备份对应放置该备份的 机器必然要被读取 2次 N[x]+=2
x为 w[i].n[0]，即从w中取得该备份所在机器的索引文件只有 2 个备份判断第一个备份所在机器的读取时间是否大于第二个备份所在机器的读取时间，如果大于，则第二个备份所在机器读取+1，否则第一个备份所在机器+1暂时不知道对不对
32 0 22 1 22 0 1 首先0号文件从第一台copy1号文件从第二台copy2号文件从第一台copy输出2 正确的应该是1
我运行了下，结果是1
表示只会二分答案网络流。
我觉得这么贪心是错的。。
是说重复地二分然后最大匹配吗？
那这组数据呢？33 1 2 30 0
只看了题目没写想了好久没有好方法。原来只有1拷贝的时候策略必然是定死的，该机器时间+22拷贝时假设在不同的机子上a,b各有一个拷贝就抽象成 边(a,b),存起来维护一个有向图每次加入一条边时 ta+1,在机器a点添加有向边a-&b如果ta&=当前MAX,不管，继续添加边，否则寻找一条路径 a-&c且tc&MAX,然后 ta-1,tc+1,MAX不变，然后把a-&c经过的边设置为反向。如果找不到这样的路径就MAX+1。但是这样写起来蛋疼，复杂度也不好说。好像也就是跟网络流的想法差不多。
二分加最大流吧……不确定超不超时……
想到几个贪心都被自己cha掉了，最后只能上二分加网络流。后来发现可以把一些边删除改造成二分加二分图多重匹配。但是感觉都卡啊，总共110000个点啊。去年acm福州regional网络赛有道十万个点的网络流，貌似也是二分图，希望有奇迹发生把
我是这样做的：机器0 2 0 2机器1 2 1 2机器2 2 0 1文件索引
0 1 2机器索引
第0备份机器索引
第1备份文件总数
2 2 2从文件0开始，发现文件0已经有2个备份了，这个时候必然有造成一个读取操作，耗时1，关键是从哪个选然后判断 文件0 中的 第0备份 所在机器0被读取的次数是否大于 文件0 中的 第1备份 所在机器2 的读取次数，如果大于，则 机器2读取++，这里 机器2读取++文件1 中的 第0备份 所在机器1被读取次数 小于 文件1中的 第1备份所在机器2 机器1读取++文件2 中的 第0备份 所在机器0被读取次数 小于 文件2中的 第1备份所在机器1 机器0读取++很明显取机器读取最大耗时是1
感觉是对的...
很明显是6呀机器0 1 2 3机器1机器2文件索引 1 2 3机器索引 0 0 0文件总数 1 1 1对于只有一个副本存在于一台机器0上，该机器上的那个副本始终要被读取 2 次，算下来就是6咯
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或}