题解 P5835 【[USACO19DEC]Meetings S】
kradcigam
2020-03-03 18:01:14
# 前言
这道题目是道好题，想通了之后就可以把轻松这道题做出来。
# 正文
## 结论
先把一个结论写出来。
无论所有奶牛怎么走，它们的体重从左往右组成的序列是不会发生改变的。
这个结论简单地说明一下。
1. 首先我们可以把 $2$ 头牛相遇看成 $2$ 头牛走的方向不变，只是交换了体重。
2. 如果这些奶牛的体重从左往右组成的序列发生改变，一定是 $2$ 头牛相向而行，然后发生序列变化。但是现在我们可以把交换体重看做**如果序列发生变化，就将 $2$ 数交换，不让序列发生改变。**
## 分析
### 二分·时间
有了这个性质，就好办了。
我们发现时间是有单调性的，然后我们就可以二分时间。
```cpp
int ll=0,rr=INT_MIN>>1;
while(ll+1<rr){
int mid=(ll+rr)>>1;
if(check(mid))rr=mid;
else ll=mid;
}
```
至于 $check$ 怎么写呢？
我们先要把 $a$ 数组是 **按位置从小到大排序。**
```cpp
sort(a+1,a+n+1,cmp);
```
$cmp$：
```cpp
bool cmp(node x,node y){
return x.x<y.x;
}
```
先放一下代码。
```cpp
bool check(int x){
int llll=1,rrrr=n,s=0;
for(int i=1;i<=n;i++)
if(a[i].d==1)s+=a[i].x+x>=l?a[rrrr--].w:0;//如果能到，重量就是a[rr--].w
else s+=a[i].x-x<=0?a[llll++].w:0;//如果能到，重量就是a[ll++].w
return s*2>=sm;
}
```
其实就是
```cpp
bool check(int x){
int ll=1,rr=n,s=0;
for(int i=1;i<=n;i++)
if(a[i].d==1){
if(a[i].x+x>=l)s+=a[rr--].w;//如果能到，重量就是a[rr--].w
}else{
if(a[i].x-x<=0)s+=a[ll++].w;//如果能到，重量就是a[ll++].w
}
return s*2>=sm;
}
```
解释一下，有人可能会
问：
> 程序里的体重不一定对啊？
答：
> 最后的体重显然是
>
> $\sum\limits_{i=1}^{k1} w_{i}+\sum\limits_{i=k2}^{n} w_{i}$
>
> 因为最后到达牛棚的，一定是达到 $0$ 的若干个，到达 $L$ 的若干个，再联系一下上面的性质，就显然是这个式子了。当然我们的 $a$ 数组是 **按位置从小到大排序的。**
### 二分·查找
我们知道了时间，距离 $AC$ 还需要找到奶牛相遇的对数的总数。
现在，我们的 $a$ 数组已经按位置从小到大排序了。
我们从左往右扫过去，我们知道，相遇的对数 $=$ 往左走的奶牛所碰到往右走的奶牛的数量之和。
那么碰到的往右走的奶牛的数量之和，我们可以用**二分**来统计。
```cpp
for(int i=1;i<=n;i++){
if(a[i].d==-1){//向左走
int xx=a[i].x-rr*2;//这里注意速度是1+1=2
int lll=0,rrr=k+1;//二分，注意边界
while(lll+1<rrr){
int mid=(lll+rrr)>>1;
if(f[mid]>=xx)rrr=mid;
else lll=mid;
}
ans+=k-rrr+1;
}else{
f[++k]=a[i].x;
}
}
```
这里的二分是在找**能与这头向左走的牛相遇的最左边的牛。**
这里的 $f$ 数组是记录向右走的牛。
## 总代码
```cpp
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
template<typename T>void write(T x){
if(x<0)putchar('-'),x*=-1;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int MAXN=5e4+10;
struct node{
int w,x,d;
}a[MAXN];
int n,l,sm,f[MAXN],k,ans;
bool cmp(node x,node y){
return x.x<y.x;
}
bool check(int x){
int ll=1,rr=n,s=0;
for(int i=1;i<=n;i++)
if(a[i].d==1)s+=a[i].x+x>=l?a[rr--].w:0;
else s+=a[i].x-x<=0?a[ll++].w:0;
return s*2>=sm;
}
int main(){
read(n);read(l);
for(int i=1;i<=n;i++)read(a[i].w),read(a[i].x),read(a[i].d),sm+=a[i].w;
sort(a+1,a+n+1,cmp);
int ll=0,rr=INT_MAX>>1;
while(ll+1<rr){
int mid=(ll+rr)>>1;
if(check(mid))rr=mid;
else ll=mid;
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i].d==-1){
int xx=a[i].x-rr*2;
int lll=0,rrr=k+1;
while(lll+1<rrr){
int mid=(lll+rrr)>>1;
if(f[mid]>=xx)rrr=mid;
else lll=mid;
}
ans+=k-rrr+1;
}else{
f[++k]=a[i].x;
}
}cout<<ans;
return 0;
}
```
# 后记
总体来讲，这道题目细节比较多，思维难度也比较高。
所以，如作者有错误请在评论区指出，谢谢。