狗家阳谷昂赛特

tianjiayou 发表于 2019-8-21 02:56
我觉得还是有问题，这种做法我想过;
看下我这个例子；这里2是7的parent（实在是不好画 lol）1是2,3,4,5 ...

没有问题啊，345的height都是3，而2的height是2，所以先入345，再入2,6。下面是我跑的结果
0
243
15
6
total：4

zzwzzw435 发表于 2019/08/21 03:25:17


没有问题啊，345的height都是3，而2的height是2，所以先入345，再入2,6。下面是我跑的结果
0
243
15
6
total：4

哦哦，好像是可以的，我想错了

搜索到的澳洲選舉制度, 我沒看明白.....:

在澳大利亚的选票上，所有候选人的名字是按照改名的字母顺序排列的，选民在选择的时候，不是在选票上划钩，而是按照个人的喜好在选票上写序号。比如，在悉尼所在地的新南威尔士州某选区有六名候选人A、B、C、D、E、F。从这六人当中选出一名议员，不是在六人中只选一个就行了，你得按喜好程度在六个人名字前标出1、2、3、4、5、6。如：A-3,B-5,C-1,D-4,E-6,F-2。也就是说，你最希望C当选，其次是F，然后是A，依此类推是D、B，最后才是E。这是优先票选的含义。

在计票的时候则采取转移计票的原则，即instant runoff voting和transferable counting(或叫 transferable distribution )。这个更复杂。

在统计选票时，要和先看有没有候选在这一轮就有超过半数的选民把他作为第一选择，即得到“1”的票数是否超过一半。如果有，那么这位就当选了。如果没有，就统计得“1”票最少的。比如，该选区共有三万张选票，C得到了40%的“1”票，即一万二千票，F得35%计10500张选票。而E得票最少，只有10%，即3000张。那么E在第一轮计票时就被淘汰了。而选择E为首选的选票并不作废，要看他们的第二选择是谁。如果在选E的3000张选票中，有1000张把C当作第二选择，那么这1000张选票就要加到C名下。如果C在第一轮得到了12000张选票的话，这时，他的得票就有13000张了。其余的人则选择了F作为第二优选，那么其余的2000张票就要计到F的名下，这样，F就拥有了12500张选票，两人还是没有过半数，那就再淘汰一名候选人。候选人B，得到20%即6000张选票，同样，这些人中，有1000人选择了C作为第二选择，而把另有5000把F作为第二选择，这样的票加起来，C得到14000张选票，F则拥有了17500张选票。依此类推下去，最后的结果可能是在第一轮计票中领先的C并没有得率先得到超过半数的选票，反而是F率先得到了三万张以上的选票，那么，尽管C在第一轮计票中是领先的，那他也不能当选，相反是F当选了

zzwzzw435 发表于 2019-8-21 02:41
感觉还是可以做，和indegree，outdegree并没有太大关系
[mw_shl_code=java,true]class Solution {
     ...

网上查了一下，有个叫Hu's算法（ucsd 教授），和你这一样，不过只能是树。我想找一个DAG让这个算法失败，刚刚找到一个可以失败的，应该还有更好的例子，这里我找到的：

假设k为10
一共30个任务，1～30
1～10 做完才能做11
12做完才能做13～30

如果用胡的算法，就可以先做1～10,然后 11， 12, 然后两轮做完13～30，一共四轮
最优的会考虑13～30都被12挡住，可以先做1～9+12, 然后10, 13～21, 然后11, 22～30, 一共三轮

我想会有更好的反例，不过还没有想出来。。。

补充内容 (2019-9-17 10:07):
刚想出一定失败的例子，改成40个就好了。

k=10
1～10 做完才能做11，11做完才能做12
13做完才能做14～40

贪心法5步，最优4步。

jackxpeng 发表于 2019-9-17 09:02
网上查了一下，有个叫Hu's算法（ucsd 教授），和你这一样，不过只能是树。我想找一个DAG让这个算法失败， ...

那要怎么做好
不按照height来，按照number来？

sicilianee 发表于 2019-10-13 11:58
那要怎么做好
不按照height来，按照number来？

按number也不对