AtCoder Beginner Contest #085 B問題 - Kagami Mochi

Source

AtCoder Beginner Contest #085
問題文

問題概要

$N$ 個の円形の餅があり,直径はそれぞれ $D_1,D_2,\ldots,D_N$ である.
鏡餅を作るのに,何個かの餅を重ねる.
その際,一番下の餅以外は,直下の餅より半径が厳密に小さくなければならない.
最大で何段の鏡餅を作れるかを求める問題.

解法

異なる直径の餅が何個あるかを求めれば良い.
後は大きい順に下から置いていけば良いので.
時間計算量は $O(N + \max(D_i)-\min(D_i))$ や $O(N \log N)$ などでできる.

cLayversion 20180107-1)のコード

C++に変換後のコードはこちら

int N, D, arr[101];
{
  int res;
  
  rd(N);
  rep(N){
    rd(D);
    arr[D]=1;
  }
  res = sum(arr(101));
  wt(res);
}

Current time: 2018年07月17日01時09分29秒
Last modified: 2018年01月07日22時58分30秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC085 ABC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン: