网站维护是什么专业,网页设计基础课心得体会2000字,wordpress 一键安装包,模糊背景网站POJ 3253 Fence Repair 题目链接#xff1a;http://poj.org/problem?id3253 题目大意 农夫约翰想修理牧场周围的一小段篱笆。他测量了栅栏#xff0c;发现他需要N(1≤N≤20,000)块木板#xff0c;每块长度为整数Li(1≤Li≤50,000)。然后#xff0c;他买了一块长木板#…POJ 3253 Fence Repair 题目链接http://poj.org/problem?id3253 题目大意 农夫约翰想修理牧场周围的一小段篱笆。他测量了栅栏发现他需要N(1≤N≤20,000)块木板每块长度为整数Li(1≤Li≤50,000)。然后他买了一块长木板刚好能看到N块木板(即它的长度是长度Li的和)。FJ忽略了“kerf”即锯切时锯屑损失的额外长度;你也应该忽略它。 FJ悲哀地意识到他没有锯子来锯木头于是他拿着这块长木板来到农民Don的农场礼貌地问他是否可以借把锯子。 法默·唐是一个隐蔽的资本家他不借给FJ一把锯子而是提出要向法默·约翰收取木板上N-1个缺口的费用。切一块木头的费用正好等于它的长度。切一块长21英寸的木板要21美分。 然后让农夫唐决定砍木板的顺序和地点。帮助农民约翰决定他能花多少钱来制作N块木板。FJ知道他可以将木板切割成不同的顺序这将导致不同的收费因为中间木板的长度是不同的。 分析 此题是一道经典的霍夫曼编码问题可以每次选两块最小的木板不放回再将相加之和的作为新木板放回木板集合中即可 #includeiostream
#includealgorithm
using namespace std;
const int maxn 20005;
int w[maxn];
int n;
typedef long long ll;
bool cmp(int a, int b) {return a b;
}
void solve() {for (int i 0; i n; i)cin w[i]; ll ans 0;while (n 1) {int mii1 0, mii2 1;if (w[mii1] w[mii2])swap(mii1, mii2);for (int i 2; i n; i) {if (w[i] w[mii1]) {mii2 mii1;mii1 i;}else if (w[i] w[mii2]) {mii2 i;}}int t w[mii1] w[mii2];ans t;if (mii1 n - 1)swap(mii1, mii2);w[mii1] t;w[mii2] w[n - 1];n--;}coutansendl;
}int main() {freopen(shuru.txt, r, stdin);ios::sync_with_stdio(false);cin n;solve();return 0;
} 转载于:https://www.cnblogs.com/ACMerLwy/p/11268394.html
