题解：CF2111D Creating a Schedule

zhangmuning1016 · 2025-06-16 14:52:03 · 题解

题意

新学期第一天要为 n 个班级排课表，每个班级有 6 节课，每节课同时进行且需安排在不同班级不能同时使用的教室。教室编号除最后两位外的数字表示楼层（如 479 在 4 楼）。要求最大化所有班级跨楼层移动总次数，移动按最短路径计算。需为每个班级输出 6 个教室编号，满足每节课时每个教室仅被一个班级使用。

思路

我觉得你直觉够强，一眼能看出做法，所以我直接上代码。

为最大化跨楼层移动次数，要让每个班级在不同楼层间切换。

• 按楼层分组，同一层教室归为一组。
• 对于每个班级的 6 节课，安排在两个楼层间的教室，这样每次上课都需跨楼层移动，这样 6 节课会有 5 次切换。
• 若楼层组不足两组，则同一楼层内安排，此时无跨楼层移动。

  代码

  注意：第 15 行前加上 while(s>=100)s/=10;。

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  signed main() {
  int t;
  cin>>t;
  while(t--) {
      int n,m;
      cin>>n>>m;
      vector<int>a(m);
      for(int i=0; i<m; ++i)
          cin>>a[i];
      vector<pair<int,int> >v;
      for(int x:a) {
          int s=x;
          v.emplace_back(s,x);
      }
      sort(v.begin(),v.end());
      vector<int>g[m];
      int c=0;
      if(v.size()) {
          g[0].push_back(v[0].second);
          for(int i=1; i<v.size(); ++i) {
              if(v[i].first==v[i-1].first)
                  g[c].push_back(v[i].second);
              else g[++c].push_back(v[i].second);
          }
          ++c;
      }
      vector<int>ptr(c,0);
      for(int i=0; i<n; ++i) {
          int g1=i%c,g2=(i+1)%c;
          vector<int> ans;
          for(int j=0; j<6; ++j) {
              if(j%2==0) {
                  ans.push_back(g[g1][ptr[g1]%g[g1].size()]);
                  ptr[g1]++;
              } else {
                  ans.push_back(g[g2][ptr[g2]%g[g2].size()]);
                  ptr[g2]++;
              }
          }
          for(int x:ans)cout<<x<<" ";
          cout<<endl;
      }
  }
  return 0;
  }