题解：P14765 [ICPC 2024 Seoul R] Bottles

KellyH · 2025-12-16 19:52:19 · 题解

:::align{center}

Bottles

:::

序

洛谷题目链接

思路

1. 时间轴：对每个选手，计算其通过每个路段的时间区间。
2. 事件点：收集所有选手进入和离开各路段的时间点，这些时间点将时间轴分割为若干不重叠的开区间。
3. 区间统计：遍历每个时间区间，统计该区间内每个路段的选手数量，最后更新各路段的最大值就可以了。

   代码

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int MAXN=105;
   const int MAXM=305;
   ll in_time[MAXN][MAXM]; 
   ll out_time[MAXN][MAXM]; 
   vector<ll> events; 
   int max_bottles[MAXM]; 
   int n,m;
   int main()
   {
   cin>>n>>m;
   // 步骤1：计算每个选手通过各路段的时间区间
   for(int i=0;i<n;i++)
   {
       ll total=0; 
       for(int j=0;j<m;j++)
       {
           ll t;
           cin>>t;
           in_time[i][j]=total; 
           out_time[i][j]=total+t; 
           total+=t; // 更新累计时间
           // 收集事件点
           events.push_back(in_time[i][j]);
           events.push_back(out_time[i][j]);
       }
   }
   // 步骤2：去重并排序事件点，分割时间轴为开区间
   sort(events.begin(),events.end());
   events.erase(unique(events.begin(),events.end()),events.end());
   // 步骤3：遍历每个时间区间，统计各路段选手数
   int k=events.size();
   for(int i=0;i<k-1;i++)
   {
       ll L=events[i];
       ll R=events[i+1];
       if(L==R)continue; 
       // 统计当前区间 [L, R]内各路段的选手数
       int cnt[MAXM]={0};
       for(int p=0;p<n;p++)
       { 
           for(int j=0;j<m;j++)
           { 
               if(in_time[p][j]<R&&out_time[p][j]>L)
               {
                   cnt[j]++;
               }
           }
       }
       // 更新各路段的最大选手数
       for(int j=0;j<m;j++)
       {
           max_bottles[j]=max(max_bottles[j],cnt[j]);
       }
   }
   for(int j=0;j<m;j++)
   {
       cout<<max_bottles[j];
       if(j<m-1)
       {
           cout<<" ";
       }
   }
   cout<<endl;
   return 0;
   }