少年Q

用户名：yin19990129

访问量：25370

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

25.智慧之轮-题解(C++代码)只做最好的思路！
浏览：250

26.网络互通-题解(C++代码)只做最好的思路！
浏览：559

27.阴阳（C++代码）只做最好的思路！
浏览：317

你可能喜欢

25.智慧之轮-题解(C++代码)只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-03-22 20:33:38 浏览：250　|　评论：0　

原题链接：智慧之轮

这题还是要用堆来做的，如果用容器会出问题，貌似容器没有办法消除一个元素，只是将元素挪至下一位，那么新元素进来，被消除的元素依旧参与排序，从而进行干扰。
当然对于容器，我也不太熟练，这样的理解也只是个人看法，我容器试了两次，都是时间超限67%。
第一次用容器超限67%，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
multiset<int>v;

int main(){
	int n,m,k;
	cin>>n;
	while(n--){
		cin>>m;
		if(m==3){
			cin>>k;
			v.insert(k);
		}else if(m==2){
			cin>>k;
			v.erase(*v.end()+1);
			v.insert(k);
		}else{
			cout<<*v.begin()<<endl;
			v.erase(v.begin());
		}
	} 
	v.clear();
	return 0;
}
```
后来修改容器后，依旧超限67%，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
multiset<int>v;

int main(){
	int n,m,k,p=1;
	cin>>n;
	while(n--){
		cin>>m;
		if(m==3){
			cin>>k;
			v.insert(k);
			p++;
		}else if(m==2){
			cin>>k;
			v.erase(*v.begin()+p);
			v.insert(k);
		}else{
			cout<<*v.begin()<<endl;
			v.erase(v.begin());
			p--;
		}
	} 
	v.clear();
	return 0;
}
```
后来跟着老师傅学堆，这次呢，老师傅终于给出了代码，但。。。也太长了吧，心里苦啊，后来看了大神网友的堆代码，果然不错，简洁高效，跟着大神的代码码了一遍，这个堆的模板，大家可以多看看，以后可以跟着这个模板码堆，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int heap[5005],pos=0;
void up(int p){
	int f;
	while(p/2>0){
		f=p/2;
		if(heap[p]<heap[f]){
			swap(heap[p],heap[f]);
		}else{
			break;
		}
		p=p/2;
	}
}

void insert(int x){
    pos++;
	heap[pos]=x;
	up(pos);	
}

void down(){
	int f=1,mark,l,r;
	l=2*f;
	r=2*f+1;
	while(l<=pos){
		if(l==pos){
			mark=l;
		}else if(l<pos){
			if(heap[l]<heap[r]){
				mark=l;
			}else{
				mark=r;
			}
		}
		if(heap[mark]<heap[f]){
			swap(heap[mark],heap[f]);
		}else{
			break;
		}
		f=mark;
		l=2*f;
		r=2*f+1;
	}
}

void mod(int x){
	int max=1;
	for(int i=2;i<=pos;i++){
		if(heap[max]<heap[i]){
			max=i;
		}
	}
	heap[max]=x;
	up(max);
}

void pop(){
	cout<<heap[1]<<endl;
	heap[1]=heap[pos];
	pos--;
	down();
}

int main(){
	int n;
	int x,xi;
	cin>>n;
	while(n--){
		cin>>x;
		if(x==1){
			pop();
		}else if(x==2){
			cin>>xi;
			mod(xi);
		}else if(x==3){
			cin>>xi;
			insert(xi);
		}
	}
	return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C语言代码）

1028

小九九（C语言代码）

第一

25.智慧之轮-题解(C++代码)只做最好的思路！

评论区

精彩推荐

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

拆分位数（C语言代码）

数组输出（C语言代码）错误？？？

A+B for Input-Output Practice (II) （C语言代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

少年Q

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C语言代码）

1028

小九九 （C语言代码）

第一

25.智慧之轮-题解(C++代码)只做最好的思路！

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

拆分位数 （C语言代码）

数组输出 （C语言代码）错误？？？

A+B for Input-Output Practice (II) （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-温度转换（C语言代码）

小九九（C语言代码）

　　评论区

母牛的故事（C语言代码）

拆分位数（C语言代码）

数组输出（C语言代码）错误？？？

C语言训练-求函数值（C语言代码）