\(solution\)
首先此题如果不考虑重量,那么我们可以忽略每头牛的个性。从整体来看,如果两头牛相遇可以看作他们穿过对方并继续前进。但如果每头牛有不同的重量,那么它们就有了个性,不能再等价于穿过对方。
这时候我们从两个角度来考虑:
\(1.\) 如果有\(x\)头牛回窝,那么一定是靠近端点的\(x\)头牛。原因很简单,这是一个一维的空间,前面的牛不回窝后面的就会被堵住过不去。所以每头牛回窝的顺序就确定了。
\(2.\) 在\(T\)时刻内,一头牛只可能与他迎面走来的\(2 \times T\)距离内的牛相遇。这个时候我们不需考虑重量,所以每头牛可以看作穿过相遇的对方继续前进,那么显然\(T\)时刻内这两头牛相向而行\(2 \times T\)的距离。
通过第一个推论我们可以二分求出时刻\(T\)。通过第二个推论我们可以根据\(T\)来求出相遇的牛的总数。
注意求相遇时对于第\(i\)头牛,维护一个\(x_i+2 \times T\)以内的区间,可以前缀和预处理一下。
时间复杂度\(O(n log n)\)
\(Code\)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
register int s=0,f=1;
register char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}
while(isdigit(ch))s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*f;
}
const int N=50005;
int n,L,sum;
struct node{int w,x,d;}a[N];
bool comp(node a,node b){
return a.x<b.x;
}
bool check(int x){
int ll=0,rr=0;
for(int i=1;i<=n;i++){
int tmp=a[i].x+a[i].d*x;
if(tmp<=0)ll++;
if(tmp>=L)rr++;
}
int tot=0;
for(int i=1;i<=ll;i++)tot+=a[i].w;
for(int i=n-rr+1;i<=n;i++)tot+=a[i].w;
return tot*2>=sum;
}
int ans,f[N];
int Bound(int x){
int ll=0,rr=n+1;
while(ll+1<rr){
int mid=(ll+rr)>>1;
if(a[mid].x<=x)ll=mid;
else rr=mid;
}
return ll;
}
void solve(int t){
for(int i=1;i<=n;i++){
if(a[i].d==-1)f[i]=f[i-1]+1;
else f[i]=f[i-1];
}
for(int i=1;i<=n;i++){
if(a[i].d==-1)continue;
int p=Bound(a[i].x+2*t);
ans+=f[p]-f[i];
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
n=read(),L=read();
for(int i=1;i<=n;i++){
a[i].w=read(),a[i].x=read(),a[i].d=read();
sum=sum+a[i].w;
}
sort(a+1,a+n+1,comp);
int ll=0,rr=1e9;
while(ll+1<rr){
int mid=(ll+rr)>>1;
if(check(mid))rr=mid;
else ll=mid;
}
solve(rr);
return 0;
}