社区讨论

关于 MLE

学术版参与者 5已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mhj1uf18
此快照首次捕获于
2025/11/03 19:21
4 个月前
此快照最后确认于
2025/11/03 19:21
4 个月前
查看原帖
校内模拟赛的题目,考察反悔贪心,我写了如下代码:
CPP
#include<bits/stdc++.h>
using std::cin;using std::cout;using std::priority_queue;using std::vector;using std::greater;
int t,n,m,k,a;
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		priority_queue<int,vector<int>,greater<int> > pq;
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++){
			cin>>a;
			if(k){
				k--;
				pq.push(a);
			}
			else if(pq.size()&&pq.top()<a){
				m-=pq.top();
				pq.pop();
				pq.push(a);
			}
			else{
				m-=a;
			}
			if(m<=0){
				cout<<i-1<<'\n';
				break;
			}
		}
		if(m>0) cout<<n<<'\n';
	}
	return 0;
}
然而不知为何 MLE 了,以下是 std,跑得飞快
CPP
#include<bits/stdc++.h>
using namespace std;
void solve() {
	long long n,x,k;
	scanf("%lld%lld%lld",&n,&x,&k);
	priority_queue<long long,vector<long long>,greater<long long> > pq;
	int ans=-1;
	for(int i=1; i<=n; i++) {
		long long in;
		scanf("%lld",&in);
		if(k) {
			k--;
			pq.push(in);
		}
		else if(pq.size() && pq.top()<in) {
			x-=pq.top();
			pq.pop();
			pq.push(in);
		}
		else {
			x-=in;
		}
		if(x<=0 && ans==-1) ans=i-1;
	}
	if(ans==-1) ans=n;
	printf("%d\n",ans);
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}
已知 n105n\le10^5,看了好久,感觉 push 操作的地方都一模一样,求问 MLE 的原因。

回复

10 条回复,欢迎继续交流。

正在加载回复...