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

- 日理万妓 2022-09-10 11:09 94阅读 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 条评论，94人围观）

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

相关阅读

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

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

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

相关了解时间复杂度分析

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

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

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

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

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

相关致互联网人：内卷之王诞生了！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

╰+哭是因爲堅強的太久メ/ 2022年09月04日 09:45/ 0 赞/ 258 阅读

相关致互联网人：内卷之王诞生了！

互联网内卷之风盛行原因是什么？通过互联网人的：以前、后来、现在或许能够找到答案和播妞一起来看 —— ![05ee11e25dc9fe334c10

深藏阁楼爱情的钟/ 2022年08月29日 00:07/ 0 赞/ 210 阅读

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

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

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

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

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

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

相关时间复杂度分析

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

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

相关《新喜剧之王》

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

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

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

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

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