自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:04:24，当前版本为作者最后更新于2024-09-28 01:15:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先根据输入找出所有必须被安排的座位，并计算它的数量（设为 $cnt$）。如果这个数大于 $m$ 则肯定不行，输出 Impossible。

否则，先把 $cnt$ 个乘客安排好，剩下 $m'=m-cnt$ 个乘客。因为座位必须是对称的，所以左边有一个座位，右边就必须也有一个，即如果有安排的方案，$m'$ 必须是偶数。如果是奇数就无解。

接下来就直接模拟，从飞机第一排开始往后分别给乘客排好座位即可，记得判断最后会不会有飞机座位不够的情况。

#include<bits/stdc++.h>
using namespace std;
bool a[1145][7];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=6;j++){
			char c;cin>>c;
			if(c=='X')a[i][j]=1;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=6;j++){
			if(a[i][j]&&!a[i][7-j])cnt++,a[i][7-j]=1;
		}
	}
	if(cnt>m)cout<<"Impossible",exit(0);
	m-=cnt;
	if(m%2)cout<<"Impossible",exit(0);
	for(int i=1;i<=n&&m;i++){
		for(int j=1;j<=6&&m;j++){
			if(a[i][j]==0)m-=2,a[i][j]=a[i][7-j]=1;
		}
	}
	if(m)cout<<"Impossible",exit(0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=6;j++){
			cout<<((a[i][j])?('X'):('.'));
		}cout<<endl;
	}
	return 0;
}

注：代码中 m-=cnt; 前后两行的判断删去也能 AC，这是因为在后面的模拟中，如果 $m'$ 不符合要求，则代码中的变量 m 一定不会被减到 $0$。