NC21719. 座位预定
描述
输入描述
第一行包含一个整数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; }