Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Japan 2011 予選 B問題 - 最高のコーヒー (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 予選 B問題

問題概要

問題分が日本語なので略.

解法

時間を逆から遡ると,飲めるコーヒーの種類は増えていく一方なので,飲めるコーヒーのうちもっとも満足度の高いものを飲めば良い.
ヒープなどを使えばO(N log N).
以下の解答は,賞味期限の早いものから順番に飲んでいって,賞味期限切れで飲めなかった,今まで飲んだ満足度が一番小さいのを飲むのを取り消していく.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

void intIntSort(ll d[],ll m[],ll s){
  ll i=-1,j=s,k,t;
  if(s<=1)return;
  k=(d[0]+d[s-1])/2;
  for(;;){
    while(d[++i]<k);
    while(d[--j]>k);
    if(i>=j)break;
    t=d[i];d[i]=d[j];d[j]=t;
    t=m[i];m[i]=m[j];m[j]=t;
  }
  intIntSort(d,m,i);
  intIntSort(d+j+1,m+j+1,s-j-1);
}

void intIntIntSort(ll d[],ll m1[],ll m2[],ll s){
  ll i=-1,j=s,k,t;
  if(s<=1)return;
  k=(d[0]+d[s-1])/2;
  for(;;){
    while(d[++i]<k);
    while(d[--j]>k);
    if(i>=j)break;
    t=d[i];d[i]=d[j];d[j]=t;
    t=m1[i];m1[i]=m1[j];m1[j]=t;
    t=m2[i];m2[i]=m2[j];m2[j]=t;
  }
  intIntIntSort(d,m1,m2,i);
  intIntIntSort(d+j+1,m1+j+1,m2+j+1,s-j-1);
}

int main(){
  ll i,j,k,l,m,n,now;
  ll c[120], t[120], s[120], use[120];
  ll res;
  ll val[120], ind[120];
  
  int size,count=0;

  scanf("%d",&size);
  while(size--){
    scanf("%lld%lld",&n,&k);
    rep(i,n) scanf("%lld%lld%lld",c+i,t+i,s+i);
    rep(i,n) use[i] = 0;

    intIntIntSort(t,c,s,n);

    rep(i,n) val[i] = s[i], ind[i] = i;
    intIntSort(val,ind,n);
    
    now = 0;
    rep(i,n){
      k = t[i] - now;
      if(k > c[i]) k = c[i];

      use[i] += k;
      now += k;

      rep(m,n){
        j = ind[m];
        if(s[j] >= s[i]) continue;
        
        k = use[j];
        if(k > c[i]-use[i]) k = c[i]-use[i];

        use[j] -= k;
        use[i] += k;
      }
    }

    res = 0;
    rep(i,n) res += use[i] * s[i];
    printf("Case #%d: %lld\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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