Running Median
Running Median
https://ac.nowcoder.com/acm/problem/50940
题意:输出数组 的中位数
懵逼的题解:每次数组 排序...
我不知道为什么这个能过,
时间复杂度:
我怎么算这个时间复杂度也会炸的呀.......
//ac code #include<bits/stdc++.h> typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int p; cin>>p; while(p--) { int t,m; int ans=0; cin>>t>>m; int a[m+5]; cout<<t<<" "<<m/2+1<<'\n'; for(int i=0;i<m;i++) cin>>a[i]; for(int i=0;i<m;i++) { if((i+1)%2!=0) { sort(a,a+i+1); if(ans==0) cout<<a[i/2]; else cout<<" "<<a[i/2]; ans++; if(ans==10) { ans=0; cout<<'\n'; } } } if(p!=0) cout<<'\n'; } return 0; }
正常的题解:建立最大堆,最小堆(可以直接写优先队列,不用手动建堆)
把每次输入的元素压入最大堆和最小堆中,然后进行两个堆的调整,如果两个堆的堆顶值不同,那么连个堆堆顶值全部弹出,然后再交换压入,最后可以达到的效果是
大根堆存储的是数组
小根堆存储的是数组
其中
以上数字为调整后的数字大小,只用作举例说明,并且大根堆小根堆的数组长度相同,而且此处假设原数组为
堆是什么呢 https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin ---来自百度百科
时间复杂度:
正常一点可以过的时间复杂的
#include<bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while(T--) { priority_queue<int,vector<int>, greater<int> > que_1; //小顶堆 priority_queue<int> que_2; int kk, n, x; cin >> kk >> n; cout << kk << ' ' << (n+1)/2 << endl; for(int i = 1; i <= n; i++) { cin >> x; que_1.push(x); que_2.push(x); if(i%2==0) continue; while(que_1.top() != que_2.top()) { int a = que_1.top(); int b = que_2.top(); que_1.pop(), que_2.pop(); que_1.push(b); que_2.push(a); } cout << que_2.top() << ' '; if(((i+1)/2)%10 == 0) cout << "\n"; else if((n%2==1&&i==n) || (n%2==0&&i==n-1)) cout << "\n"; } } return 0; }
上面的第一个题解更新之前能过,现在数据已经更新