問題はこちら
No.549 素材合成システム - yukicoder
合成素材の側の経験値の最終的な寄与度は高々floor(a/2)
実際に、一番経験値が高い奴をベースにし、残りを素材として順次合成していくことで最大になる。
c(int*a,int*b){return*b-*a;} a[100010],n,S; main(){ scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",a+i); qsort(a,n,4,c); S=a[0]; for(int i=1;i<n;i++)S+=a[i]/2; printf("%d",S); }
ソートしなくても、最大値を記憶しておくことで先頭から順に読み込むことができる
#define max(p,q)(p>q?p:q) t,n,M,S; main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&t); M=max(M,t); S+=t/2; } printf("%d",S-M/2+M); }
式を変形して最後の出力をS-~M/2にできる
ぎゅっとする
s,x,m; main(i){ for(;~scanf("%d",&x);)--i?m<x?m=x:0,s+=x/2:0; printf("%d",s-~m/2); }
80B