首页 > 代码库 > POJ - 3253 Fence Repair(贪心)

POJ - 3253 Fence Repair(贪心)

2024-09-27 08:30:02   218人阅读

题目链接：http://poj.org/problem?id=3253

题意：哈夫曼最优编码

贪心策略：尽可能让花费大的路径短。

总花费=每个花费*路径之和。也等于每次加上去得到的数之和。（每次都排序一下，把最小的两个相加）

 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4  5 typedef long long LL; 6 const int maxn=20000+10; 7 int L[maxn]; 8  9 int main(){10     int N;11     cin>>N;12     for(int i=0;i<N;i++) cin>>L[i];13     LL ans=0;14     while(N>1){15         int temp1=0,temp2=1;16         if(L[temp1]>L[temp2]) swap(temp1,temp2);17         for(int i=2;i<N;i++){18             if(L[i]<L[temp1]){19                 temp2=temp1;20                 temp1=i;21             }22             else if(L[i]<L[temp2]){23                 temp2=i;24             }25         }26         int t=L[temp1]+L[temp2];27         ans+=t;28         L[temp1]=t;29         L[temp2]=L[N-1];30         N--;31     }32     cout<<ans<<endl;33     return 0;34 }

 

POJ - 3253 Fence Repair(贪心)


联系
我们