社区讨论

求 hack

P11231[CSP-S 2024] 决斗参与者 7已保存回复 9

讨论操作

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

当前回复
8 条
当前快照
1 份
快照标识符
@m2ssqn1k
此快照首次捕获于
2024/10/28 17:08
去年
此快照最后确认于
2025/11/04 15:48
4 个月前
查看原帖
以下是一个理论复杂度 O(n2)O(n^2) 的代码,但是我自己没有办法把它卡掉。
vectorerase(begin())O(n)O(n)的。
最慢的点 150ms,本地极限数据 0.2s
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,r[N];
vector<int> v;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)r[i]=read();
	sort(r+1,r+1+n);
	int ans=n;
	for(int i=1;i<=n;i++){
		if(!v.empty()&&r[i]>v[0]){
			ans--;
			v.erase(v.begin());
		}
		v.push_back(r[i]);
	} 
	cout<<ans;
	return 0;
}
 

回复

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

正在加载回复...