卷王之王（优先队列 + 时间复杂度分析）

- 日理万妓 2022-09-10 11:09 17阅读 0赞

**题意：** 给定 n 个数， 接下来 m 次操作，每次输入一个 x ，如果数列中存在小于等于x的值，则加上x

**错误 ：** 用优先队列操作，优先队列操作对象是第一个字符，当然也可以自己定义。

**题解：** 把小于等于x 的数字取出来，放入vector中，然后依次进行加法，之前的想法是用一个while，但是会加多次而不是一次。

**分析：** 因为x值是有限定的，每个数 a\[I\] += x ，最多加log(x) 次， 然后这个数就比x的范围大了，永远不会再出队列。

**时间复杂度**： m \* log(n) \* log(x)

默认是大跟堆， 注意小跟堆的构造方式

#include<bits/stdc++.h>
    using namespace std;
    #define ff first
    #define ss second
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    typedef long long ll;
    typedef pair<ll,ll> PII;
    
    const int N = 1e5 + 10;
    
    ll n, m, a[N];
    vector<PII> v;
    
    void solve()
    { 
    	priority_queue <PII,vector<PII>,greater<PII> > q;
    	
    	cin >> n >> m;
    	
    	rep(i,1,n) 
    	{ 
    		ll tmp; cin >> tmp;
    		q.push({ tmp,i});
    	}
    	
    	rep(i,1,m)
    	{ 
    		ll x; cin >> x;
    		if(x==0) continue;
    		while(q.size() and q.top().ff <= x) 
    			v.push_back(q.top()), q.pop();
    		int len = v.size();
    		rep(i,0,len-1)
    		{ 
    			auto f = v[i];
    			f.ff += x;
    			q.push(f);
    		}
    		v.clear();
    	}
    	
    	while(q.size())
    	{ 
    		auto t = q.top();
    		q.pop();
    		a[t.ss] = t.ff;
    	}
        
    	rep(i,1,n) cout << a[i] << " ";
    }
    
    int main()
    { 
    	solve();
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关时间、空间复杂度分析

时间复杂度 `时间复杂度`表示算法的执行时间与数据规模之间的增长关系。虽然代码千差万别，但是常见的复杂度量级并不多。我稍微总结了一下，这些复杂度量级几乎涵盖了你今后可

偏执的太偏执、/ 2023年07月25日 14:24/ 0 赞/ 10 阅读

相关了解时间复杂度分析

以例子来说更好的理解先了解一下大O表示法 int cal(int n) { int sum = 0; int i = 1;

淡淡的烟草味﹌/ 2023年05月30日 06:27/ 0 赞/ 31 阅读

相关「算法」时间、空间复杂度分析

1. 衡量算法性能的标准数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如

喜欢ヅ旅行/ 2022年11月06日 03:54/ 0 赞/ 287 阅读

相关卷王之王（优先队列 + 时间复杂度分析）

题意：给定 n 个数，接下来 m 次操作，每次输入一个 x ，如果数列中存在小于等于x的值，则加上x 错误：用优先队列操作，优先队列操作对象是第一个字符，当然也可以自

- 日理万妓/ 2022年09月10日 11:09/ 0 赞/ 18 阅读

相关【算法二】—— 时间复杂度分析

解决同一个问题可以有很多种算法，比较评价算法的好坏，一个重要的标准就是算法的时间复杂度。现在研究一下插入排序算法的执行时间，按照习惯，输入长度LEN以下用n表示。设循环中各条语

超、凢脫俗/ 2022年05月30日 08:16/ 0 赞/ 339 阅读

相关数据结构之时间.空间复杂度分析

include <iostream> include <assert.h> using namespace std; / 在很

爱被打了一巴掌/ 2022年05月25日 10:53/ 0 赞/ 199 阅读

相关算法分析（时间复杂度和空间复杂度）

算法分析（时间复杂度和空间复杂度）对于一个给定的算法需要做两项分析，第一就是证明算法的正确性，第二就是计算算法的复杂度。算法的复杂度包括时间复杂度和空间复杂度。 1

梦里梦外;/ 2022年04月22日 14:24/ 0 赞/ 313 阅读

相关时间复杂度分析

时间复杂度分析我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那

痛定思痛。/ 2022年04月14日 03:23/ 0 赞/ 279 阅读

相关《新喜剧之王》

刚刚看完了《新喜剧之王》，觉得跟以前的《喜剧之王》不是一个风格，电影中讲述了一个女孩子为了当演员奋斗的故事，觉得感触也颇深的，最初和一个女孩住着合租房，后来那个女孩出名了以后，

拼搏现实的明天。/ 2021年12月23日 22:19/ 0 赞/ 176 阅读

相关排序算法之时间复杂度、空间复杂度

<table> <thead> <tr> <th>排序算法</th> <th>最好时间</th> <th>平均时间</th> <th>

￡神魔★判官ぃ/ 2021年09月18日 04:22/ 0 赞/ 586 阅读