Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Yandex Open 2011 Qualification 1 C問題 - Average Score (この記事を編集する[管理者用])

Source

Yandex Open 2011 Qualification 1 C問題 (1500pt)
Problem description
Yandex Open 2011 Qualification 1の自分の参加記録

問題概要

n個 (100000以下) の1以上5以下の整数が与えられる.
それを2つのグループに分けたい.
片方のグループにはちょうどa個の整数,もう片方にはちょうどb個の整数を含むようにしたい.(a+b=n)
両方のグループの平均値を求め,その和を最大化したい.
そのようなグループ分けの仕方を求める問題.
複数あるなら,辞書順最小のものを求める.

解法

集合サイズが小さいほうが影響力が強いので,そっちにできるだけ大きい数字を詰め込めば良い.
後は,辞書順最小になるようにgreedyに選ぶ.

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)

int main(){
  int i,j,k,l,m;
  int n, n1, n2;
  int in[111111];
  int cnt[6];
  int nn1[6], nn2[6], go;

  while(scanf("%d%d%d",&n,&n1,&n2)==3){
    rep(i,n) scanf("%d",in+i);
    rep(i,6) cnt[i]=0;
    rep(i,n) cnt[in[i]]++;

    if(n1==n2){
      rep(i,n){
        if(i) putchar(' ');
        if(i<n1) putchar('1'); else putchar('2');
      }
      puts(""); continue;
    }

    rep(i,6) nn1[i] = nn2[i] = 0;

    go = n1; if(n1<n2) go = n2;
    rep(i,6){
      k = cnt[i];
      if(k > go) k = go;
      go -= k;
      nn1[i] += k;
      nn2[i] += cnt[i]-k;
    }

    if(n1 < n2){
      rep(i,6) k=nn1[i], nn1[i]=nn2[i], nn2[i]=k;
    }

    rep(i,n){
      if(i) putchar(' ');
      if(nn1[in[i]]>0){ putchar('1'); nn1[in[i]]--; }
      else            { putchar('2'); nn2[in[i]]--; }
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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