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$ 人グループと相席させるのは,単純に出来るだけ多くの人を消費できるようにするのが良い.
という風にやっていく.
#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: 2024年03月19日14時33分17秒
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)