Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1480-68693b6d
この記事にトラックバックする(FC2ブログユーザー)

SRM479 DIV1 EASY - TheCoffeeTimeDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM479 DIV1 EASY (250pt)
Problem Statement
SRM479 DIV1 自分の参加記録

問題概要

飛行機.n人が1列に座っていて,コーヒーかお茶を配るのにかかる時間の最小値を求める問題.
47人以下にお茶を淹れて,その人の座標が与えられる.それ以外はコーヒー.
お茶かコーヒーのどちらか片方のみ,7個以下をトレーにのせることができる.
汲む場所は最初の席の前にあり,1マス移動するのに1秒,支給するのに4秒,汲むのに47秒かかる.
nは44777777以下.

解法

後ろから順番に配っていくのが最適.
O(n)でも間に合うので,実際に後ろから眺めていって,7人に達するか,一番前まで来たグループに分けて配る時間を足していく.

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

このコードは実際に本番でサブミットしたコードを修正したものです.見にくいと思われます.

// #includeとusing namespace std;は略

#define ll long long

class TheCoffeeTimeDivOne {
public:
long long find(int n, vector <int> tea) {
  int i,j,k,st;
  ll res=0;

  sort(tea.begin(), tea.end());

  res += (tea.size() + 6)/7;
  res += (n-tea.size()+6)/7;
  res *= 47;

  res += n * 4LL;

  for(st=tea.size()-1;st>=0;st-=7) res += tea[st]*2;

  i=n; st=tea.size()-1;
  for(;i>0;){
    k=0;
    while(k<7){
      while(st>=0 && i==tea[st]) i--, st--;
      if(k==0) res += i*2;
      if(i<=0) break;
      i--; k++;
    }
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1480-68693b6d
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。