关于T3部分分
  • 板块学术版
  • 楼主2c_s
  • 当前回复17
  • 已保存回复19
  • 发布时间2024/9/7 18:05
  • 上次更新2024/9/7 21:02:34
查看原帖
关于T3部分分
583186
2c_s楼主2024/9/7 18:05

rt,第一部分分是否有卡常?还是这份代码不是目标复杂度?

const int N=1e5+10;
int n,m;
struct node{
	int x,t;
}a[N];
multiset<int>st;
vector<int>ve;
#define abs(x) ((x)>0?(x):-(x))
signed solution(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)a[i].x=read(),a[i].t=read();
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j)st.insert(abs(a[i].x-a[j].x)/abs(a[i].t-a[j].t));
	}
	while(m--){
		int u=read(),v=read();
		ve.clear();
		for(int i=1;i<=n;++i){
			if(i!=u){
				auto p=st.find(abs(a[u].x-a[i].x)/abs(a[u].t-a[i].t));
				ve.push_back(*p);
				st.erase(p);
			}
		}
		for(int i=1;i<=n;++i){
			if(i!=u)st.insert(abs(a[u].x-a[i].x)/abs(v-a[i].t));
		}
		auto p=st.end();
		--p;
		printf("%d\n",*p);
		for(int i:ve)st.insert(i);
		for(int i=1;i<=n;++i){
			if(i!=u)st.erase(st.find(abs(a[u].x-a[i].x)/abs(v-a[i].t)));
		}
	}
	return 0;
}
2024/9/7 18:05
加载中...