当前位置: 代码迷 >> 综合 >> poj-3253-哈夫曼树
  详细解决方案

poj-3253-哈夫曼树

热度:8   发布时间:2023-12-19 11:27:35.0

题意:

John要修理牧场周围的篱笆。根据他的测量,他需要N块木板(1 <= N <= 20,000),每块都有各自的长度Li(1 <= Li <= 50,000)单位长度。于是他买了一块大木板足够切成N块木板,并且我们假设切割不会损耗任何木材。 但John没有锯子,于是他向Don借,但Don希望向John收取一定的费用,费用按照John切隔木板的实际长度计算。切隔一块长度为21的木板需要支付21美分。 John想要知道最少要花费多少钱。

做法:

把所有的需要的板子排序。取最小的加起来,放进需要的板子里面。

重复操作

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{__int64 i,n,j;__int64 a[200001];scanf("%I64d",&n);for(i=0;i<n;i++){scanf("%I64d",&a[i]);}sort(a,a+n);__int64 sum,num;sum=0;for(i=0;i<n-1;i++){num=a[i]+a[i+1];sum+=num;for(j=i+2;j<n;j++){if(a[j]<=num){a[j-1]=a[j];}else{a[j-1]=num;break;}}if(j==n)a[j-1]=num;}printf("%I64d\n",sum);return 0;
}