Znzryb's Blog
0%

2025牛客WC3-E-智乃的小球

Posted on Edited on

思路讲解

image

交换速度你可以理解为这两个球想幽灵一样，直接穿过，没有碰撞（因为我们不在乎是哪个球撞的，我们只在乎碰撞次数）

套了一个树状数组查逆序对的板子

不要用unordered_map以及set用于离散化，常数有一点大。

可以用unique，sort，以及lower_bound实现离散化，常数比较小，写也不是很难写

还有要求误差小于eps可以这么写，不用直接写<eps，快一点（卡常卡常）

1
2
3
4
5
6
7
8
while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}

双指针就是可以从暴力优化，原本是双层循环，但其实第二次循环有必要从1开始吗？显然不是对吧。

然后注意notMeet可能还是需要lower_bound()一下

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}

AC代码

双指针肯定比树状数组稍微快一点

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75219410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}

ll N,K,tr[MAXN];
DB curP[MAXN];
int idx,idx_;

int pv[MAXN],pv_[MAXN];	// 正速度，负速度
inline bool check(DB t){	// 枚举时间
	ll res=0;
	//   break的那个不要，所以notMeet初始为1
	int flag=1;     // flag=1 上次在哪里停的？
	FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}
	
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),K=read();
	FOR(i, 1, N){
		int p=read(),v=read();
		if(v<0){
			pv_[++idx_]=p;
		}else{
			pv[++idx]=p;
		}
	}
	sort(&pv[1], &pv[idx+1]);
	sort(&pv_[1], &pv_[idx_+1]);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*

4 4
1 1
2 -1
3 -1
0 1

1.5

4 1
4 1
3 -1
2 -1
1 -1

No

8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1


*/

各种卡常技巧一起上，终于是过了用树状数组。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75217361

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	int p,v;
//	bool operator<(const posv &other) const{
//		return p<other.p;
//	}
};
posv pv[MAXN];
inline bool cmp(posv a, posv b){
	return a.p<b.p;
}

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
//	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin()); // 相当于R-L+1，传进去的仍然是个数
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
//		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		ll rk=lower_bound(li.begin(), li.end(),curP[i])-li.begin()+1;
		res+=max(i-1-query(rk-1),0ll);
		add(rk);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	cin>>N>>K;
	N=read(),K=read();
	FOR(i, 1, N){
		pv[i].p=read();
		pv[i].v=read();
//		cin>>pv[i].p>>pv[i].v;
	}
	sort(&pv[1], &pv[N+1],cmp);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/

心路历程（WA，TLE，MLE……）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75218329

双指针有问题是因为这个

1
2
3
4
5
6
7
8
9
10
11
12
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {++notMeet;continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		res+=flag-notMeet;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hack数据
8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1

应该输出
22
输出
18（约）

这个程序看起来没问题，但其实有点问题，就是88理应得到0，但这个程序会给出错误判断，说明notMeet的逻辑有问题，应该使用二分查找更为保险

树状数组超时，MLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-6;

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	ll p,v;
	bool operator<(const posv &other) const{
		return p<other.p;
	}
};
vector<posv> pv(MAXN);

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin());
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		res+=max(i-1-query(rank[curP[i]]-1),0ll);
		add(rank[curP[i]]);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	FOR(i, 1, N){
		cin>>pv[i].p>>pv[i].v;
	}
	sort(pv.begin()+1, pv.begin()+N+1);
	DB l=0,r=1e9;
	while (r-l>eps) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<eps){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/