deepquiet的博客

题意: 给出n个任务的耗时和截止时间,求最多可接几单 思路: 类似的题目这几天都在做,所以很自然想到优先队列,wa了一发,原因是输出之间没有换行 先按照截止时间从小到大入队,然后耗时越多的越先出队 代码:#include #include #include #include #include #include using namespace std; const int maxn = 1

题意: 给出n个任务完成区间以及工作量,求出最快处理速度. 思路: 用二分搜索匹配最优速度,其中还用到优先队列辅助. 枚举所有截止时间,在此时间内的都进队,按照工作截止时间越早越先出队,如果截止时间不及枚举的截止时间,则错过 代码: #include #include #include #include #include using namespace std; const int N

题目: 在给定区域内放车,使得所有车在不同行且不同列(无法互相攻击) 思路: 这个和processor很像,都是在给定范围内安排事件,所以都用到了优先队列,按照前端点优先. 这里要提到由于水平和垂直的位置确定不影响,所以分开确定,即一个车的位置确定分两次. 同时用m来控制下个元素的最小放置位置，如果某元素的最远范围小于m显然是不行的。 #include #inclu

题意: 每个商品都有利润和保质期,在保质期内,能够卖出的最高利润. 思路: 显然最长时间就是所有商品中的最大保质期,时间自然是递减的,然后利用优先队列取出最大利润的商品. 枚举截止时间,商品的保质期在截止时间之后的才能入队,为了保证队内的物品不过期,截止时间应从最长时间递减. 代码: #include #include #include #include using namespace

题意: 求最短路 思路: 这里用到了邻接表来存储,由于n太大了,然后还用了优先队列来优化,每次都输出里面的最短边,如果这个点的最短边已经考虑过了自然就不会考虑,然后每纳入一个点(就是优先队列里出来的未考虑的点)就重新调整每个点到原点的距离, 所有调整过的点都重新入队 代码: #include #include #include #include using std::make_pair;