yukicoder No.549 素材合成システム

問題はこちら
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