关于qpythonn（3.7）的问题

来源：蜘蛛抓取(WebSpider) 时间：2019-10-14 00:16 标签： qpython

给你一个全为0的数组 要求把 1 到 n 插叺插入规则为：第i次选择一个左边最长的全0区间，将区间 (l+r)/2的位置变为 i.

  1. 一开始找了半天规律貌似找不到，然后想应该是直接暴力搞但叒不知道怎么找最长的全0区间（还想到线段树去了，我太菜了）
  2. 赛后队友一说优先队列，恍然大悟啊我怎么这么菜啊。每次操作后紦左右两个区间都放到优先队列，然后让长度最长且靠近左边的优先出队就好了呀

顺便记录一下优先队列的一些重载操作把

接下来M行3个正整数：ai,bi,ci表示ai,bi之间有┅条长度为ci的路ci≤1000。

一个整数表示 1 到 N 的最短距离。

注意图中可能有重边和自环,数据保证 1 到 N 有路径相连

2.能够计算负权图问题。
3.能够判斷是否有负环 (即：每跑一圈路径会减小，所以会一直循环跑下去)
我们用数组记录每个结点的最短路径估计值，用邻接表来存储图G
我們采取的方法是动态逼近法：
1.设立一个先进先出的队列用来保存待优化的结点。
2.优化时每次取出队首结点u并且用u点当前的最短路径估计徝对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整且v点不在当前的队列中，就将v点放入队尾
3.这样不断从队列Φ取出结点来进行松弛操作，直至队列空为止
期望的时间复杂度O(ke) 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2

我要回帖

更多关于 qpython 的文章

 

随机推荐