Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #3 B問題 - Lorry (この記事を編集する[管理者用])

ソース

Codeforces Beta Round #3 B問題
Problem description
Beta Round #3の自分の参加記録

問題概要

船が100000個以下ある.
それぞれの船のコストは1か2で,能力値が1以上10000以下.
合計コストがv以下で,合計能力値が最大になる組み合わせを1つ求める問題.

解法

vが奇数なら最初に1個だけ最も能力値の高いコスト1の船を入れる.
後は,
 コスト2の船の一番能力値が高いの
 コスト1の船の能力値が一番高いのと二番目に高いの
の高い方をgreedyに詰め込んでいくだけ.

C言語のスパゲッティなコード

以下のコードは実際に本番にサブミットしたコードで見にくい可能性が高いです.

以下のコードの方針は,1コストの船を何個入れて,2コストの船を何個入れるかを全通り試すコードです.
1コストの船と2コストの船を入れる数が決まれば,それぞれのコストの船は能力値の高いものから入れます.
この方針の簡単な説明は,Beta Round #3の自分の参加記録に書いています.

#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)

void intSort(int d[],int s){int 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;}intSort(d,i);intSort(d+j+1,s-j-1);}
void intIntSort(int d[],int m[],int s){int 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 intReverse(int d[],int size){int a=0,b=size-1,t;while(a<b)t=d[a],d[a]=d[b],d[b]=t,a++,b--;}

int main(){
  int i,j,k,l,m,n,v;
  int a[100000],a_ind[100000],b[100000],b_ind[100000],as,bs;
  int res_a,res_b,res;
  int na,nb,now,br=0;
  int pr[100000],ps=0;

  scanf("%d%d",&k,&n);
  as=bs=0;
  rep(m,k){
    scanf("%d%d",&i,&j);
    if(i==1) a[as]=j, a_ind[as++]=m+1;
    if(i==2) b[bs]=j, b_ind[bs++]=m+1;
  }

  intIntSort(a,a_ind,as); intReverse(a,as); intReverse(a_ind,as);
  intIntSort(b,b_ind,bs); intReverse(b,bs); intReverse(b_ind,bs);

  nb=n/2;    if(nb>bs) nb=bs;
  na=n-2*nb; if(na>as) na=as;

  res=0;
  rep(i,na) res+=a[i];
  rep(i,nb) res+=b[i];
  res_a=na; res_b=nb;
  now=res;
  
  while(nb){
    now -= b[--nb];
    if(na<as) now += a[na++];
    if(na<as) now += a[na++];

    if(now > res) res=now, res_a=na, res_b=nb;
  }

  printf("%d\n",res);
  rep(i,res_a) pr[ps++]=a_ind[i];
  rep(i,res_b) pr[ps++]=b_ind[i];
  intSort(pr,ps);
  rep(i,ps){
    if(i)putchar(' ');
    printf("%d",pr[i]);
  }
  puts("");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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