1：有n个人，要求选出一个组长来，每个人限投一票，如果有人得票率超过50%就当选，输出当选人。
要求算法O（n）。
2：网络中有关键节点，如果攻击该节点（就是将此节点删除）。请输出最小攻击节点集使得网络通讯中断。
各位有什么好的想法？

第二个好象是离散数学里的图中的一个叫做什么的.给忘了.
晕

第一个好做.
a[i]++就可以了.并记录最大者.因为只有一个才有可能超过50%.

我感觉你的想法算法复杂度比（n）大。
我在想若是采用链式的基数排序可行否。
Mayor.vector[1]-Mayor.vector[n]对应投票人。
关键码key[0],...,key[d-1]对应得到的投票。d<=n
然后选出Max key，输出对应的Mayor.vector[]

2楼说的是不是带权的图阿

第二题，我是觉得感觉和AOV的有点类似，但是还没有琢磨明白。

int data[100]={0};
int t,k=1,max=0;
for(int i=0;i<n;i++)
{
t=rand()%n+1;
data[t]++;
if(data[t]>max)
{
max=data[t];
k=t;
}
}
//Print(k,max);

时间复杂度为O(n).

赞，不错，想法比我的简化了很多。

[此贴子已经被作者于2007-4-27 23:34:44编辑过]