PAT 1125

第二题很多人都说是赫夫曼树,我就排了个序就过了,之后推敲了一下这个逻辑是可行的,当然赫夫曼树也是正解,有兴趣的同学可以用赫夫曼树做一下

#include<iostream>#include<vector>#include<string>#include<algorithm>using namespace std;int main(){	int n, i;	double s[10005], len = 0;	scanf("%d", &n);	for (i = 0; i < n; i++) {		scanf("%lf", &s[i]);	}	sort(s, s + n);	len = s[0];	for (i = 1; i < n; i++) {		len = len / 2 + s[i] / 2;	}	int l = (int)(len);	if (l <= len) {		PRintf("%d/n", l);	}	else {		printf("%d/n", l - 1);	}	return 0;}