2025牛客WC3-E-智乃的小球 · znzryb
## 思路讲解
交换速度你可以理解为这两个球想幽灵一样，直接穿过，没有碰撞（因为我们不在乎是哪个球撞的，我们只在乎碰撞次数）
套了一个树状数组查逆序对的板子
不要用unordered_map以及set用于离散化，常数有一点大。
可以用unique，sort，以及lower_bound实现离散化，常数比较小，写也不是很难写
还有要求误差小于eps可以这么写，不用直接写<eps，快一点（卡常卡常）
```cpp
while (r-l>(eps*l)) {
DB mid=(l+r)/2.0;
if(check(mid)){
r=mid;
}else{
l=mid;
}
}
```
双指针就是可以从暴力优化，原本是双层循环，但其实第二次循环有必要从1开始吗？显然不是对吧。
然后注意notMeet可能还是需要lower_bound()一下
```cpp
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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75219410)
```cpp
#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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75217361)
```cpp
#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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75218329)
双指针有问题是因为这个
```cpp
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;
}
```
```cpp
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
```cpp
#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
*/
```