自动搬运

查看原文

来自洛谷，原作者为

	warmingcium 当 默认随机引擎 遇上 统一实数分布

搬运于2025-08-24 22:03:07，当前版本为作者最后更新于2023-10-29 14:40:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

差一点点就抢到最优解啦~

题意简述

飞机座位共有 $n$ 排可以坐，第 $1$ 排前面、第 $\frac{n}{2}$ 排后面以及最后一排后面是安全通道，一排有 $9$ 个座位依次编号为$ABC.DEF.GHI$。

在安全通道后面第一排的位置应先进行安排，当安全通道后面第一排位置都安排满了，每一排空位越多越先安排；若多排空余位置数目相同，越靠近安全通道越先安排；如果距离安全通道距离相同，则应从前往后安排。你在安排一排座位的时候安排顺序为：当 $D F$ 空的时候先安排 $D F$ ，然后 $C G$ 空的时候安排 $C G$ ，$A I$空的时候安排 $A I$， $E$ 空的时候安排 $E$ ，$B H$ 空的时候安排 $B H$ 。

当两个位置的优先级相同并且可以都可以安排的时候，如果左方人数小于等于右方人数的时候先安排左方的位置，否则先安排右方的位置。

模拟策略

1. 安全通道后面第一排先安排。

2. 每一排空余位置越多越先安排。

3. 距离安排通道越近越先安排。

4. 字典序小的先安排。

5. 每一排按照给定的顺序安排。

6. 飞机两边哪边人数小哪边安排，相等安排在左方。

代码实现

• 我用变量 $cntR$ 记录每一排有多少个空余的位置。
• 用变量 $cntl$ 记录飞机左边有多少人。
• 用变量 $cntr$ 记录飞机右边有多少人。
• 用变量 $dir$ 记录每一排的安排顺序。
• 用变量 $dis$ 记录每一排距离安全通道的距离。

依照上述模拟策略，我们只需要按照 $26$ 个字母顺序把对应的人放进去即可，只要读题没有问题并且有亿点点耐心调试都没有问题啦~

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int maxm = 19;
char s[maxn][maxm];
int n,m,cntR[maxn],cntl,cntr,dir[10]={0, 5, 3, 1, 6, 2},dis[maxn];
int findR(){
    int Max=-1,R=0;
    if(cntR[2] == 0 && cntR[3+n/2] == 0){
        for(int i = 1; i <= n+3; i++){
            if(cntR[i] > Max){
                Max = cntR[i];
                R = i;
            } else if(cntR[i] == Max) {
                if(dis[i]<dis[R]) {
                    R=i;
                }
            }
        }
    }else{
        if(cntR[2] >= cntR[3+n/2]) return 2;
        else return 3+n/2;
    }
    return R;
}
int findC(int R) {
    for(int i=1;i<=5;i++) {
        int now=dir[i];
        int pos1=now;
        int pos2=12-now;
        if(s[R][pos1]=='-'&&s[R][pos2]=='-') {
            if(cntl<=cntr) return pos1;
			else return pos2;
        } else if(s[R][pos1] == '-') {
            return pos1;
        } else if(s[R][pos2] == '-') {
            return pos2;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+3;i++) {
        scanf("%s",s[i]+1);
        int cnt=0;
        for(int j=1;j<=11;j++){
            if(s[i][j]=='-') cnt++;
            if(s[i][j]=='#') {
                if(j<=5) cntl++;
                if(j>=7) cntr++;
            }
        }
        if(i<3+n/2) dis[i] = min(i-1, (2+n/2)-i);
		else dis[i]=min(i-(2+n/2), (n+3)-i);
        cntR[i]=cnt;
    }
    for(int i=0;i<m;i++){
        int R=findR();
        int C=findC(R);
        if(C<6) cntl++;
        else if(C>6) cntr++;
        s[R][C]=i+'a';
        cntR[R]--;
    }
    for(int i=1;i<=n+3;i++) {
        printf("%s\n",s[i]+1);
    }
    return 0;
}