一道简单的模拟

· · 题解

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

题意简述

飞机座位共有 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. 飞机两边哪边人数小哪边安排，相等安排在左方。

代码实现

依照上述模拟策略，我们只需要按照 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;
}