列表

详情


NC21719. 座位预定

描述

    众所周知,ACMore编程协会的团支书ppq是矿里有家的大土豪,每次出去参加比赛都是选择飞机出行。这次他和他的小伙伴出去比赛当然也是选择了飞机出行(有钱真好,我为什么哭了QAQ)。
    在登机之前,都是要对座位进行选择的,选择座位自然不是乱选的。ppq通过查阅了解到大多数人都是按照以下的规则进行选择座位的。
    我们假设一架飞机上总共有r+3排的座位,从前往后编号为1~r+3,其中有3排为安全出口通道(分别为第1排,第r/2+2排,第r+3排),所以这3排是无法坐人的。每一排都固定占有11个位置,其中有9个位置是可以坐人的,座位号从左往右为ABC.DEF.GHI(大写字母代表可以坐的座位,‘.’代表这是过道)。
    大多数人会以如下的规则进行座位的选择:
    1、首先是选择坐在哪一排,如果安全出口通道后面一排(第2排和第r/2+3排)还有空座位,那么就会选择这一排,如果有多种选择的话,他会优先选择空座位较多那一排;如果还是有多种选择的话,他就会选择编号较小的那一排;
    2、如果安全出口通道后面一排没有空座位了,他就会选择空座位数量最多的那一排;如果有多种选择的话,他就会选择最靠近安全出口通道的那一排;如果还是有多种选择的话,他会选择编号较小的那一排;
    3、选择完排之后就会开始选择座位,乘客首先会根据座位的舒适度从高到低选择座位,座位的舒适度从高到低的排行如下:
    (1) 位于飞机中间且靠近过道的座位(即座位D和F)
    (2) 位于飞机两侧且靠近过道的座位(即座位C和G)
    (3) 位于飞机靠窗位置的座位       (即座位A和I)
    (4) 位于飞机中间且在中间的座位  (即座位E)
    (5) 位于飞机两侧且在中间的座位   (即座位B和H)
    如果按照舒适度选完座位之后仍有多种选择的话,他会选择能平衡飞机重量的位置。如果已选择坐在飞机左侧的人数大于已选择坐在飞机右侧的人数的话,他就会选择坐在飞机右侧,否则他就会选择坐在飞机左侧。(飞机的左侧为第1~5列,右侧为第7~11列)。
    了解了这个规则之后,ppq知道他们这次的航班的飞机上总共有r+3排的座位,同时也知道了一部分人选择座位的情况,现在还有n个人(用小写字母表示)要进行选座,这n个人按顺序依次选择座位(即a最先选择座位,依次排下去,直到最后一个人)。好奇的ppq想知道如果这n个人按照根据选择座位的规则进行选择座位的话,最终飞机上的座位情况会是怎么样呢?聪明的ACMer能帮帮ppq吗?

输入描述

第一行包含一个整数T(),表示总共有T组测试样例
第二行包含了两个整数r()和n(),表示ppq所乘坐的飞机有r+3排座位,同时又n个乘客要对座位进行选择。
接下来r+3行,每行包含11个字符。
输入的字符仅包含以下3种:
‘.’:表示过道或者安全出口通道,这个位置无法坐人;
‘-’:表示空座位;
‘#’:表示这个座位已经被人选了,无法再选择这个座位;
数据保证输入的‘-’个数大于等于n。

输出描述

对于每组样例:
第一行输出一行“Case #x:”,x表示当前为第几组样例(详细见样例);
接下来,输出一个(r+3)*11的矩阵,表示最后飞机上的座位安排情况。

示例1

输入:

1
2 17
...........
---.#--.---
...........
---.---.---
...........

输出:

Case #1:
...........
hnd.#lb.fpj
...........
kqg.cma.eoi
...........

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

Java(javac 1.8) 解法, 执行用时: 53ms, 内存消耗: 14208K, 提交时间: 2020-08-10 21:56:37

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		int r, n;
		for (int i = 0; i < T; ++i) {
			r = in.nextInt();
			n = in.nextInt();
			char seat[][] = new char[r + 3][11];
			int cnt[] = new int[r + 3];

			int left = 0, right = 0;
			for (int j = 0; j < r + 3; ++j) {
				seat[j] = in.next().toCharArray();
				if (j == 0 || j == r / 2 + 1 || j == r + 2) {
					continue;
				}
				for (int k = 0; k < 11; k++) {
					if (seat[j][k] == '-') {
						++cnt[j];
						if (k < 5)
							++left;
						if (k > 5)
							++right;
					}
				}
			}
			for (int k = 0; k < n; ++k) {
				int row = turn(seat, r, n, cnt);
				int value[] = { 3, 1, 4, 0, 5, 2, 5, 0, 4, 1, 3 };
				for (int j = 0; j < 11; j++) {
					if (seat[row][j] != '-') {
						value[j] = 0;
					}
				}
				int max = value[0];
				int index = 0;
				for (int j = 1; j < value.length; j++) {
					if (max < value[j]) {
						max = value[j];
						index = j;
					}
				}

				if (seat[row][10 - index] == '-') {
					if (left < right) {
						if (index < 5) {
							index = 10 - index;
						}
					} else {
						if (index > 5) {
							index = 10 - index;
						}
					}
				}

				if (index < 5)
					--left;
				if (index > 5)
					--right;
				seat[row][index] = (char) ('a' + k);
				--cnt[row];
			}

			System.out.printf("Case #%d:\n", i + 1);
			for (int j = 0; j < r + 3; j++) {
				System.out.println(seat[j]);
			}
		}
		in.close();
	}

	private static int turn(char[][] seat, int r, int n, int[] cnt) {
		if (cnt[1] == 0 && cnt[r / 2 + 2] == 0) {
			int max = cnt[1];
			int index = 1;
			for (int i = 2; i < cnt.length; i++) {
				if (max == cnt[i]) {
					int dis_m = dist(index, r);
					int dis_i = dist(i, r);
					if (dis_m > dis_i) {
						index = i;
					}
				}
				if (max < cnt[i]) {
					max = cnt[i];
					index = i;
				}
			}
			return index;
		} else {
			if (cnt[1] < cnt[r / 2 + 2]) {
				return r / 2 + 2;
			} else {
				return 1;
			}
		}
	}

	private static int dist(int i, int r) {
		int _1 = i;
		int _2 = Math.abs(i - (r / 2 + 1));
		int _3 = Math.abs(i - (r  + 2));
		return ((_1 < _2) ? ((_1 < _3) ? _1 : _3) : ((_2 < _3) ? _2 : _3));
	}
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-09-20 11:08:16

#include <bits/stdc++.h>
using namespace std;
char s[54][12];
int vis[54];
int tmp[5][2]={{5,7},{3,9},{1,11},{6,6},{2,10}};
int getRow(int r){
    int ans,M=0;
    for(int i=1;i<=r+3;i++){
    	if(vis[i]==0||vis[i]<M) continue;
        else if(M<vis[i]){
            M=vis[i];
            ans=i;
        }else if(M==vis[i]){
            int r1=min(abs(i-1),abs(i-r/2-2));
            r1=min(r1,abs(i-r-3));
            int r2=min(abs(ans-1),abs(ans-r/2-2));
            r2=min(r2,abs(ans-r-3));
            ans=r1<r2?i:ans;
        }
    }
    return ans;
}
int getCol(int a,int b,int L,int R,int row){
    if(s[row][a]=='-'&&s[row][b]!='-') return a;
    else if(s[row][a]!='-'&&s[row][b]=='-') return b;
    else if(s[row][a]=='-'&&s[row][b]=='-') return L>R?b:a;
    else return -1;
}
int main(){
    int T,q=1,r,n,L=0,R=0,row,col;
    scanf("%d",&T);
    while(q<=T){
        scanf("%d %d",&r,&n);
        for(int i=1;i<=r+3;i++)vis[i]=0;
        for(int i=1;i<=r+3;i++){
            for(int j=1;j<=11;j++){
                cin>>s[i][j];
                if(s[i][j]=='-')vis[i]++;
                if(s[i][j]=='#'&&j<=5)L++;
                else if(s[i][j]=='#'&&j>=7)R++;
            }
        }
        printf("Case #%d:\n",q++);
        for(int i=0;i<n;i++){
            char c='a'+i;
            if(vis[2]>0&&vis[r/2+3]==0) row=2;
            else if(vis[2]==0&&vis[r/2+3]>0) row=r/2+3;
            else if(vis[2]>0&&vis[r/2+3]>0){
                row=vis[2]<vis[r/2+3]?r/2+3:2;
            }else{
                row=getRow(r);
            }
          for(int i=0;i<5;i++){
            int box=getCol(tmp[i][0],tmp[i][1],L,R,row);
            if(box==-1) continue;
            else{col=box;break;}
          }
            s[row][col]=c;vis[row]--;
            if(col<=5)L++;
            else if(col>=7) R++;
        }
        for(int i=1;i<=r+3;i++){
            for(int j=1;j<=11;j++){
                printf("%c",s[i][j]);
            }
            printf("\n");
        }
        L=R=0;
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 516K, 提交时间: 2023-05-01 22:04:08

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
using namespace std;
int r,n;
string s[60];
int num[60]; // 剩余座位数量 

int calcdis(int x){ // 离安全出口通道的距离 
	int ans=1e9+10;
	ans=min(ans,abs(x-1));
	ans=min(ans,abs(x-(r/2+2)));
	ans=min(ans,abs(x-(r+3)));
	return ans;
} 

int getr(){ // 选择坐在哪一排
	if(num[2]>0 && num[r/2+3]>0){
		if(num[2]>=num[r/2+3])return 2;
		else return (r/2+3);
	} else if (num[2]>0){
		return 2;
	} else if (num[r/2+3]>0){
		return (r/2+3);
	} else { // 安全出口通道后面一排没有空座位了
		int maxp=3;
		int dis=calcdis(3);
		int mindis=dis;
		for(int i=4;i<=r+2;i++){
			if(i==r/2+2)continue; // 安全出口通道
			
			dis=calcdis(i); // 离安全出口通道的距离 
			if(num[i]>num[maxp] || (num[i]==num[maxp] && dis<mindis)){
				maxp=i;
				mindis=dis;
			}
		}
		return maxp;
	}
	
//	cerr<<"ERROR"<<endl;
	return 2; 
}
const int rank1[15]={4,2,0,5,1};
int numleft=0,numright=0;

int getx(int r1){ // 选择坐在哪一列 
	for(int i=0;i<5;i++){
		int rk=rank1[i]; 
		if(s[r1][rk]=='-' && s[r1][10-rk]=='-'){
			if(numleft>numright)return 10-rk;
			else return rk;
		} else if (s[r1][rk]=='-'){
			return rk;
		} else if (s[r1][10-rk]=='-'){
			return 10-rk;
		}
	}
	return 0;
}

int main(){ // 模拟 
	ios::sync_with_stdio(0); cin.tie(0);
	int t; 
	cin>>t;
	for(int Case=1;Case<=t;Case++){
		// 初始化 
		numleft=0; numright=0; 
		memset(num,0,sizeof num);
		
		 
		cin>>r>>n;
		for(int i=1;i<=r+3;i++){
			cin>>s[i];
		}
		for(int i=1;i<=r+3;i++){
			for(int j=0;j<11;j++){
				if(s[i][j]=='-'){ // 空座位 
					num[i]++;
				} else if (s[i][j]=='#'){
					if(j<5)numleft++;
					else if(j>5)numright++;
				}
			}
		}
		
		for(int i0=1;i0<=n;i0++){ // 枚举每个人 
			int r1=getr(); // 选择坐在哪一排		
			int x1=getx(r1); // 选择坐在哪一列 

			s[r1][x1] = (char)('a'+i0-1);
			num[r1]--;
				
			if(x1<5)numleft++;
			else if(x1>5)numright++;
		}

		cout<<"Case #"<<Case<<":"<<endl;
		for(int i=1;i<=r+3;i++){
			cout<<s[i]<<endl;
		}
	}
	return 0;
}

上一题