标签：1000010 arr 滚动 int 弹珠 线段 碰撞
- 题目描述
链接：https://ac.nowcoder.com/acm/contest/43844/E
在一条长度为 n 的线段上，有 m 颗弹珠在匀速左右滚动，在 1 单位时间内，每颗弹珠能滚动 1 单位距离。第 i 颗弹珠由两个参数 di,pi描述，di是一个值为 0 或 1 的整数，表示弹珠初始向左滚动/向右滚动；pi是一个 1 到 n 之间的正整数，表示弹珠初始从线段上 pi位置出发。
由于只有一条线段，两颗滚动方向相反的弹珠位置重合的时候就会停滞 1 单位时间不滚动，并交换两颗弹珠滚动的方向。需要注意的是，一颗弹珠可以反复发生碰撞，如果在停滞中受到碰撞，则停滞时间会累加。如果一颗弹珠滚到了位置 0 或位置 n+1，那么这颗弹珠就滚出了线段。
请问最后一颗弹珠在什么时候滚出线段？可以证明所有弹珠都会在某个整数时刻滚出线段。
- 分析
当两个小球发生碰撞的时候，它们的前进的方向交换，但我们可以看成两个小球没有发生碰撞，而是互相穿过了彼此，假设小球此时的方向向右，位置为i，从位置i+1到位置n之间存在num个向左的小球，那么滚出线段的时间就为T = n+1-i+num,对于此题暴力的处理每一个小球滚出线段的时间最后取最大值即可，对于num的计算只需要维护一个前缀1的前缀和与后缀0的前缀和即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f0[1000010];
int f1[1000010];
int b0[1000010];
int b1[1000010];
struct node{
int d,p;
bool operator <(const node& a) const{
return a.p>p;
}
}arr[1000010];
int main(){
cin>>n>>m;
for(int i = 1;i<=m;i++) cin>>arr[i].d;
for(int i = 1;i<=m;i++) cin>>arr[i].p;
sort(arr+1,arr+1+m);
int pos = 1;
for(int i = 1;i<=n;i++){
if(arr[pos].p==i) {
if(arr[pos].d==1)
f1[i] = f1[i-1]+1,f0[i] = f0[i-1];
else
f0[i] = f0[i-1]+1,f1[i] = f1[i-1];
pos++;
}
else {
f0[i] = f0[i-1];
f1[i] = f1[i-1];
}
}
pos = m;
for(int i = n;i>=1;i--){
if(arr[pos].p==i) {
// cout<<i<<endl;
if(arr[pos].d==1)
b1[i] = b1[i+1]+1,b0[i] = b0[i+1];
else
b0[i] = b0[i+1]+1,b1[i] = b1[i+1];
pos--;
}
else {
b0[i] = b0[i+1];
b1[i] = b1[i+1];
}
}
int ans = -1;
int num = 0;
for(int i = 1;i<=m;i++){
if(arr[i].d==0){
num = arr[i].p + f1[arr[i].p];
ans = max(ans,num);
}
else{
num = n+1-arr[i].p+b0[arr[i].p];
ans = max(ans,num);
}
}
cout<<ans<<endl;
}
标签：1000010,
arr,
滚动,
int,
弹珠,
线段,
碰撞
From： https://www.cnblogs.com/wujw11world/p/16840066.html