题解：CF2111D Creating a Schedule

题意

新学期第一天要为

n

个班级排课表，每个班级有

6

节课，每节课同时进行且需安排在不同班级不能同时使用的教室。教室编号除最后两位外的数字表示楼层（如

479

在

4

楼）。要求最大化所有班级跨楼层移动总次数，移动按最短路径计算。需为每个班级输出

6

个教室编号，满足每节课时每个教室仅被一个班级使用。

思路

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

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

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

代码

注意：第

15

行前加上 while(s>=100)s/=10;。

CPP

#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;
}

题解：CF2111D Creating a Schedule

文章操作

题意

思路

代码

相关推荐

评论

题解：CF2111D Creating a Schedule