题解：P14711 [ICPC 2023 Tehran R] Pistons

· · 题解

题目大意

有 n 个活塞在 [0,m] 区间内运动，速度相同。每个活塞在碰到边界 0 或 m 时会立即反弹。给定每个活塞的初始位置和初始方向（上U或下D），求所有活塞位置之和的最大值。

解题思路

已知 n \leq 10^5，m \leq 10^6，总时间 2m 秒，直接按时间模拟每秒运动会超时。

观察：

  1. 所有活塞运动周期均为 2m，因此只需考虑 t \in [0,2m) 的情况。
  2. 所有活塞位置之和 S(t) 是一个分段线性函数，其斜率 k(t) 仅在某个活塞撞墙（碰到边界）的时刻发生改变。
  3. 在任意两个相邻的撞墙时刻之间，S(t) 线性变化，因此最大值一定出现在某个撞墙时刻或时间段的端点。

思路：

撞墙时间计算

设活塞初始位置为 p，方向为 d（+1 表示上，-1 表示下）：

注意：若活塞初始位于边界（p=0 或 p=m），则第一次撞墙时间 t_1=0，该事件可不记录。

事件扫描流程

  1. 读入数据，计算初始总和 sum 和初始斜率 slp = \sum_{i=1}^n d_i（其中 d_i 表示第 i 个活塞的初始方向，+1 表示向上，-1 表示向下）。
  2. 为每个活塞计算撞墙时间 t_1、t_2（只保留 t \in [0,2m) 的时间），加入事件列表。
  3. 将事件按时间排序。
  4. 初始化当前时间 lst=0，当前总和 cur=sum，答案 ans=cur。
  5. 遍历每个事件点 now：
    • 计算从 lst 到 now 的总和增长：cur \leftarrow cur + slp \cdot (now - lst)，更新 ans \leftarrow \max(ans, cur)。
    • 处理所有在 now 时刻撞墙的活塞：对每个活塞，方向取反 d \leftarrow -d，斜率 slp 相应更新（若原方向为上则 slp \leftarrow slp - 2，否则 slp \leftarrow slp + 2）。
    • 更新 lst = now。
  6. 处理最后一段 [lst,2m)：cur \leftarrow cur + slp \cdot (2m - lst)，更新 ans \leftarrow \max(ans, cur)。

代码实现

#include<bits/stdc++.h>
#define miao main
using namespace std;
struct ev{
  int t,id;
};//事件结构体：t时间，id活塞编号
bool cmp(ev a,ev b){
  return a.t<b.t;
}//按时间从小到大排序 
int p[100005],d[100005];//p:位置，d:方向(1上/-1下)
char dc[100005];//dc:方向字符
vector<ev> e;//事件列表
long long sum=0,slp=0;//sum:初始总和，slp:斜率(向上数-向下数)
int miao(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>p[i]>>dc[i];
        sum+=p[i];
        if(p[i]==0){
            d[i]=1;//底端必向上
        }else if(p[i]==m){
            d[i]=-1;//顶端必向下
        }else{
            d[i]=(dc[i]=='U')?1:-1;
        }
        slp+=d[i];
    }
    for(int i=0;i<n;i++){
        if(d[i]==1){//初始向上
            int t1=m-p[i];//第一次撞顶端时间
            int t2=t1+m;//第二次撞底端时间
            if(t1>0&&t1<2*m){
                e.push_back({t1,i});
            }
            if(t2>0&&t2<2*m){
                e.push_back({t2,i});
            }
        }else{//初始向下
            int t1=p[i];//第一次撞底端时间
            int t2=t1+m;//第二次撞顶端时间
            if(t1>0&&t1<2*m){
                e.push_back({t1,i});
            }
            if(t2>0&&t2<2*m){
                e.push_back({t2,i});
            }
        }
    }
    sort(e.begin(),e.end(),cmp);
    long long cur=sum,ans=cur;//cur:当前总和
    int lst=0,pos=0;//lst:上一事件时间，pos:事件指针
    while(pos<e.size()){
        int now=e[pos].t;//当前事件时间
        cur+=slp*(now-lst);//线性增长
        if(cur>ans){ans=cur;}
        while(pos<e.size()&&e[pos].t==now){//处理同一时间所有事件
            int id=e[pos].id;
            if(d[id]==1){slp-=2;}//上变下，斜率减2
            else{slp+=2;}//下变上，斜率加2
            d[id]=-d[id];//方向反转
            pos++;
        }
        lst=now;
    }
    cur+=slp*(2*m-lst);//最后一段
    if(cur>ans){
        ans=cur;
    }
    cout<<ans;
    return 0;
}