一个诡异的事情
  • 板块P1801 黑匣子
  • 楼主羊摆摇
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/10/5 14:40
  • 上次更新2023/11/4 04:45:19
查看原帖
一个诡异的事情
497817
羊摆摇楼主2021/10/5 14:40

一开始我的代码是这个亚子

#include <bits/stdc++.h>
using namespace std;

const int N=2e5;
int n,m,CQR[N],RQC[N],i=1;

priority_queue<int> X;
priority_queue<int,vector<int>,greater<int> > Y;

void cqr(int &x){
	if(X.size()==0){
		X.push(x);
		return;
	}
	if(X.size()==i){
		if(X.top()>x){
			Y.push(X.top());
			X.pop();
			X.push(x);
		}else{
			Y.push(x);
		}
	}else{
		if(Y.size()==0){
			X.push(x);
			return;
		} 
		if(Y.top()<x){
			X.push(Y.top());
			Y.pop();
			Y.push(x);
		}else{
			X.push(x);
		}
	}
	return;
}

void rqc(){
	X.push(Y.top());
	Y.pop();
}
int main(){
	scanf("%d%d",&n,&m);
	for(int k=1;k<=n;k++)scanf("%d",&CQR[k]);
	for(int k=1;k<=m;k++)scanf("%d",&RQC[k]);
	bool x=1;
	for(int k=1;k<=n&&x;k++){
		cqr(CQR[k]);
		while(k==RQC[i]){
			printf("%d\n",X.top());
			if(RQC[i]==RQC[i+1])rqc();
			i++;
			if(i==m+1)x=0;
		}
	}
	return 0;
} 

不要在意我的代码为什么那么怪异,从之前的题Ctrl+C下来的

结果有两个点T掉了。

后面我实在改不动了,就去揣摩题解

感觉他们的复杂度跟我差不多啊,凭什么他们能A而我不能?

这是我A的代码

#include <bits/stdc++.h>
using namespace std;

const int N=2e5;
int n,m,CQR[N+5],RQC[N+5],i=1;

priority_queue<int> X;
priority_queue<int,vector<int>,greater<int> > Y;

void cqr(int &x){
	if(X.size()==0){
		X.push(x);
		return;
	}
	if(X.size()==i){
		if(X.top()>x){
			Y.push(X.top());
			X.pop();
			X.push(x);
		}else{
			Y.push(x);
		}
	}else{
		if(Y.size()==0){
			X.push(x);
			return;
		} 
		if(Y.top()<x){
			X.push(Y.top());
			Y.pop();
			Y.push(x);
		}else{
			X.push(x);
		}
	}
	return;
}

void rqc(){
	X.push(Y.top());
	Y.pop();
}
int main(){
	scanf("%d%d",&n,&m);
	for(int k=1;k<=n;k++)scanf("%d",&CQR[k]);
	for(int k=1;k<=m;k++)scanf("%d",&RQC[k]);
	bool x=1;
	for(int k=1;k<=n&&x;k++){
		cqr(CQR[k]);
		while(k==RQC[i]){
			printf("%d\n",X.top());
			if(RQC[i]==RQC[i+1])rqc();
			i++;
			if(i==m+1)x=0;
		}
	}
	return 0;
} 

看出差别没有?

CQR[N],RQC[N]
CQR[N+5],RQC[N+5]

az...雀噬狃臂 不过我不李姐,这不是RE吗,肾么时候变为TLE了?

为了这个我在时间上废了不少苦工,没想到是数组大小开错了

有没有哪位dalao蚌我说明一下,以免lg故技重施Orz

2021/10/5 14:40
加载中...