哈夫曼|POJ 3253 Fence Repair （哈夫曼编码基础）哈夫曼|贪心

POJ 3253

用了哈夫曼编码的思想
参考博客：http://blog.csdn.net/lyy289065406/article/details/6647423
【哈夫曼|POJ 3253 Fence Repair （哈夫曼编码基础）】

#include #include #include #include #include using namespace std; long long L[20010]; int main() { int n; while(~scanf("%d", &n)) { int i, j; for(i = 0 ; i < n; i++) { scanf("%I64d", L + i); } sort(L, L + n); long long minn = 0, sum; for(i = 0; i < n - 1; i++) { //n - 1 次后就剩下一根木棍了，此时停止 sum = L[i] + L[i + 1]; minn += sum; for(j = i + 2; j < n; j++) { if(sum > L[j]) { L[j - 1] = L[j]; //向后移动 if(j == n - 1) {//到了最后一根时放最后 L[j] = sum; } } else { L[j - 1] = sum; //找到位置 break; } } } printf("%I64d\n", minn); } return 0; }

挑战程序设计竞赛，代码：

#include #include #include #include using namespace std; int a[20100]; int main() { int n; while(~scanf("%d", &n)) { int i, j; for(i = 0; i < n; i++) { scanf("%d", a + i); } long long ans = 0; while(n > 1) { int mini1 = 0, mini2 = 1; if(a[mini1] > a[mini2]) swap(mini1, mini2); for(i = 2; i < n; i++) { if(a[mini1] > a[i]) { mini2 = mini1; mini1 = i; } else if(a[mini2] > a[i]) { mini2 = i; } } int sum = a[mini1] + a[mini2]; ans += sum; if(mini1 == n - 1) swap(mini1, mini2); a[mini1] = sum; a[mini2] = a[n - 1]; n--; } printf("%lld\n", ans); } return 0; }