Csp-s模拟赛T2求调

王淞弘 · 2024 年10 月 24 日 01:04

//易知两端l r距消息持有者x的距离为A B 且l向右 r向左所以A+B以2m/s的速度衰减
//当x和第一个人碰面之后会立刻开始反方向运动 A和B都开始以2m/s的速度衰减
//又因为所有人的移动速度都是一样的所以中间人的移动不会影响A B衰减
//且l r之一必定最晚收到消息
//得出结论所用时间为 x和别人碰面所用时间w +max(A,B)/2

//如果A!=B(x往本来就小的那边去了) 那么总是会有一端晚收到消息故用时非最短

//x到达中点而x2距中点仍然有距离T 如果x向x2移动T/2 则x去到l的距离变为A+T/2
//又因为比等x2去到中点快T/2 故用时不变但计算更加困难

//所以当A==B时两端收到消息用时也是最短且计算方便
//即应当让x和x2去到A B中点得出结论所用时间为max(x,x2)+max(A,B)/2

#include<iostream>
#include<set>
#include<cmath>
#include<cstdio>
using namespace std;
const int INF=1e5+5;
int n,q,x;
char f;
set<int> a;
int main(){
	//freopen("secret.in","r",stdin);
	//freopen("secret.out","w",stdout);
	cin>>n>>q; 
	for(int i=0;i<n;i++){
		cin>>x;
		a.insert(x);
	}
	for(int i=0;i<q;i++){
		cin>>f;
		switch(f){
			case '+':
				cin>>x;
				a.insert(x);
				break;
			case '-':
				cin>>x;
				a.erase(x);
				break;
			case '?':
				cin>>x;
				double t=0x7fffffff,l=*a.begin(),r=*a.rbegin();//获取两端元素 
				double mid=(l+r)/2.00;
				
				set<int>::iterator end=a.lower_bound(mid);//lr中点右边 
				set<int>::iterator beg=end--;//lr中点左边 
				end++;
				if(*end==x && *end!=*a.rbegin()) end++;//能非x就非x 
				if(*beg==x && *beg!=*a.begin()) beg--;//不能就说明没有比它更大/小 
				if(*end!=x && *beg!=x)
					t=min(mid-*beg,*end-mid);//找离中点最近的非x点离中点的距离 
				else if(*beg==x) t=*end-mid;//如果beg是消息持有者 那么离中点最近就是end 
				else if(*end==x) t=mid-*beg;//反之 是beg 
				else t=0;//依题意不可能 但留一手 
				
				t=max(t,abs(x-mid));//x x2都到中点所用时间 
				double ans=t;//大数据运算时精度会逐渐散失 都开float了 那就直接开double吧 
				l+=t,r-=t;//x x2去中点时l r也在靠近中点 
				ans+=(mid-l)/2.00;
				printf("%.2f\n",ans);
				break;
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

看了题解之后写的，但就是卡在第1,10个测试点,80分,找了一天了都没发现问题在哪T-T

王淞弘 · 2024 年10 月 24 日 01:05

（文件操作是自己测试的时候注释的

王天皓 · 2024 年10 月 24 日 08:40

不是，你的代码为什么没有用```cpp包住啊！！

王淞弘 · 2024 年10 月 24 日 08:49

这是什么，我是萌新，不懂啊。。

王天皓 · 2024 年10 月 24 日 08:50

//易知两端l r距消息持有者x的距离为A B 且l向右 r向左所以A+B以2m/s的速度衰减
//当x和第一个人碰面之后会立刻开始反方向运动 A和B都开始以2m/s的速度衰减
//又因为所有人的移动速度都是一样的所以中间人的移动不会影响A B衰减
//且l r之一必定最晚收到消息
//得出结论所用时间为 x和别人碰面所用时间w +max(A,B)/2

//如果A!=B(x往本来就小的那边去了) 那么总是会有一端晚收到消息故用时非最短

//x到达中点而x2距中点仍然有距离T 如果x向x2移动T/2 则x去到l的距离变为A+T/2
//又因为比等x2去到中点快T/2 故用时不变但计算更加困难

//所以当A==B时两端收到消息用时也是最短且计算方便
//即应当让x和x2去到A B中点得出结论所用时间为max(x,x2)+max(A,B)/2
#include
#include
#include
#include
using namespace std;
const int INF=1e5+5;
int n,q,x;
char f;
set a;
int main(){
//freopen(“secret.in”,“r”,stdin);
//freopen(“secret.out”,“w”,stdout);
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>x;
a.insert(x);
}
for(int i=0;i<q;i++){
cin>>f;
switch(f){
case ‘+’:
cin>>x;
a.insert(x);
break;
case ‘-’:
cin>>x;
a.erase(x);
break;
case ‘?’:
cin>>x;
double t=0x7fffffff,l=*a.begin(),r=*a.rbegin();//获取两端元素
double mid=(l+r)/2.00;

		set<int>::iterator end=a.lower_bound(mid);//lr中点右边 
		set<int>::iterator beg=end--;//lr中点左边 
		end++;
		if(*end==x && *end!=*a.rbegin()) end++;//能非x就非x 
		if(*beg==x && *beg!=*a.begin()) beg--;//不能就说明没有比它更大/小 
		if(*end!=x && *beg!=x)
			t=min(mid-*beg,*end-mid);//找离中点最近的非x点离中点的距离 
		else if(*beg==x) t=*end-mid;//如果beg是消息持有者 那么离中点最近就是end 
		else if(*end==x) t=mid-*beg;//反之 是beg 
		else t=0;//依题意不可能 但留一手 
		
		t=max(t,abs(x-mid));//x x2都到中点所用时间 
		double ans=t;//大数据运算时精度会逐渐散失 都开float了 那就直接开double吧 
		l+=t,r-=t;//x x2去中点时l r也在靠近中点 
		ans+=(mid-l)/2.00;
		printf("%.2f\n",ans);
		break;
}

}
//fclose(stdin);
//fclose(stdout);
return 0;
}

王天皓 · 2024 年10 月 24 日 08:51

[quote=“王淞弘, post:1, topic:29542, username:王淞弘”]

//当x和第一个人碰面之后会立刻开始反方向运动 A和B都开始以2m/s的速度衰减
//又因为所有人的移动速度都是一样的 所以中间人的移动不会影响A B衰减
//且l r之一必定最晚收到消息
//得出结论 所用时间为 x和别人碰面所用时间w +max(A,B)/2

//如果A!=B(x往本来就小的那边去了) 那么总是会有一端晚收到消息 故用时非最短

//x到达中点 而x2距中点仍然有距离T 如果x向x2移动T/2 则x去到l的距离变为A+T/2
//又因为比等x2去到中点快T/2 故用时不变 但计算更加困难

//所以当A==B时两端收到消息用时也是最短 且计算方便
//即应当让x和x2去到A B中点 得出结论 所用时间为max(x,x2)+max(A,B)/2
#include
#include
#include
#include
using namespace std;
const int INF=1e5+5;
int n,q,x;
char f;
set a;
int main(){
//freopen(“secret.in”,“r”,stdin);
//freopen(“secret.out”,“w”,stdout);
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>x;
a.insert(x);
}
for(int i=0;i<q;i++){
cin>>f;
switch(f){
case ‘+’:
cin>>x;
a.insert(x);
break;
case ‘-’:
cin>>x;
a.erase(x);
break;
case ‘?’:
cin>>x;
double t=0x7fffffff,l=*a.begin(),r=*a.rbegin();//获取两端元素
double mid=(l+r)/2.00;
			set<int>::iterator end=a.lower_bound(mid);//lr中点右边 
			set<int>::iterator beg=end--;//lr中点左边 
			end++;
			if(*end==x && *end!=*a.rbegin()) end++;//能非x就非x 
			if(*beg==x && *beg!=*a.begin()) beg--;//不能就说明没有比它更大/小 
			if(*end!=x && *beg!=x)
				t=min(mid-*beg,*end-mid);//找离中点最近的非x点离中点的距离 
			else if(*beg==x) t=*end-mid;//如果beg是消息持有者 那么离中点最近就是end 
			else if(*end==x) t=mid-*beg;//反之 是beg 
			else t=0;//依题意不可能 但留一手 
			
			t=max(t,abs(x-mid));//x x2都到中点所用时间 
			double ans=t;//大数据运算时精度会逐渐散失 都开float了 那就直接开double吧 
			l+=t,r-=t;//x x2去中点时l r也在靠近中点 
			ans+=(mid-l)/2.00;
			printf("%.2f\n",ans);
			break;
	}
}
//fclose(stdin);
//fclose(stdout);
return 0;

}

王天皓 · 2024 年10 月 24 日 08:51

这样子包住
你写出来了？？
%%%膜巨佬
你的头文件那？？？？？？

王淞弘 · 2024 年10 月 24 日 08:57

没写出来。。。

王淞弘 · 2024 年10 月 24 日 08:58

不知道，我点开编辑确实有头文件，但显示的时候就没有了

王天皓 · 2024 年10 月 24 日 08:58

我说你的样例过了吗？

王淞弘 · 2024 年10 月 24 日 08:59

80分，我没有样例。。

王天皓 · 2024 年10 月 24 日 09:00

???
没有样例？

王淞弘 · 2024 年10 月 24 日 09:05

啊啊，弄错了，样例过完了，没测试点数据