题目内容
（请给出正确答案）
设S={1,2,···,n}是n项广告的集合，广告i (i=1,2，···,n)有发布开始时间s(i)和截止时间d(i)，发布效益是v(i)，其中s(i)是非负整数，d(i)和v(i)是正整数，且d(1)≤d(2)≤···≤d(n). 我们的问题是：如何在S中选择一组广告A，使得A中任意两个广告都相容(时间段不重叠)且总效益最大？ （1）假设所有广告的效益都相等，试设计一个求解上述问题的算法，证明其正确性，并说明时间复杂度. （2）如果效益v(i)可以取任意正整数，设计一个算法求解这个问题，用文字说明算法的设计思想和主要步骤，分析算法最坏情况下的时间复杂度.
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
抱歉！暂无答案，正在努力更新中……
更多“设S={1,2,···,n}是n项广告的集合，广告i （i=1,2，···,n)有发布开始时间s（i)和截止时间d（i)，发布效”相关的问题
，权值w(e)表示带宽，并且假设每条边的权都不相等. 对于任意站点
,一条u-v路径P的最大带宽是
，即这条路径上的所有边的带宽的最小值. 而u与v之间的最佳带宽w(u,v)=max{w(P)|P是一条u-v路径}，即所有u-v路径带宽的最大值. 这也是u与v之间通信的最佳带宽. （1）证明存在一棵生成树，使得在这棵树中，连接每对结点u，v唯一路径的最大带宽等于u与v之间的最佳带宽. （2）设计一个找这样一棵生成树的算法，并分析算法的时间复杂度.
一个公司需要购买n个密码软件的许可证，按照规定每个月至多可以得到一个软件的许可证. 假定每个许可证目前售价都是1000元. 但是第i个许可证的售价将按照
的指数因子增长，i=1,2,···,n. 例如，第i个许可证在1个月后将是
元，2个月后将是
元，k个月后将是
元. 给定输入
. 给出一个购买许可证的顺序，以使得花费的总钱数最少. 设计一个算法求解这个问题，说明设计思想，证明其正确性并分析算法最坏情况下的时间复杂度.
，被检索的概率是
，i=1,2,···,n，且
. 检索每个文件需要从磁带的开始位置进行操作，比如文件i需要空间=310，存储在磁带的121~430单元，那么检索该文件需要的时间为430. 问如何排列n个文件而使得平均检索时间最少？设计算法求解这个问题，说明算法的设计思想，证明算法的正确性，给出算法最坏情况下的时间复杂度.
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
为非负整数。
