Yandex.Algorithm 2015 Online Finals B問題 - Bus for a Picnic

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Online Finals
問題文

問題概要

$N$ グループの人がいて,$i$ 番目のグループは $A_i$ 人からなる.
あるバスでは $1$ 列には $6$ 個の椅子並んでいて,同じグループは全員同じ列の椅子に座らなくてはいけない.
最小で何列あれば全員座れるかを求める問題.

解法

貪欲法.
座りにくい大人数のグループから考えていく.
$6$ 人グループはそのグループで一列占領.
$5$ 人グループは,できるだけ $1$ 人グループの人と相席させる.
$4$ 人グループは,できるだけ $2$ 人グループの人と相席させ,$2$ 人グループがもうないなら空いてる席に $1$ 人グループを詰める.
$3$ 人グループは,$3$ 人グループと相席させられるだけ相席.$3$ 人グループがいなくなれば,$1$ 人グループ $3$ 組か $2$ 人グループ $1$ 組とどちらと相席させるのが良いかは多少迷うが,
よく考えて見れば,$1$ 人グループと $2$ 人グループしかいなくなれば,どうやっても詰め込めるので,$3$ 人グループと相席させるのは,単純に出来るだけ多くの人を消費できるようにするのが良い.
という風にやっていく.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N;
int A[7];

int main(){
  int k, res = 0;

  reader(&N);
  while(N--){
    reader(&k);
    A[k]++;
  }

  while(A[6]>0) res++, A[6]--;
  while(A[5]>0){
    res++;
    A[5]--;
    if(A[1]>0) A[1]--;
  }
  while(A[4]>0){
    res++;
    A[4]--;
    if(A[2]>0) A[2]--; else if(A[1]>0) A[1] = max(0, A[1]-2);
  }
  while(A[3]>1){
    res++;
    A[3]-=2;
  }
  while(A[3]>0){
    A[3]--;
    res++;
    if(A[2] && A[1]){ A[2]--; A[1]--; continue; }
    if(A[1] >= 3){ A[1] -= 3; continue; }
    if(A[2]){ A[2]--; continue; }
    A[1] = max(0, A[1]-3);
  }

  res += (A[1] + 2*A[2] + 5) / 6;
  writerLn(res);

  return 0;
}

Current time: 2017年07月23日15時43分29秒
Last modified: 2015年08月15日14時01分13秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Finals
トップページに戻る

Logged in as: unknown user (not login)

ログイン: