Description
Farmer John wants
to repair a small
length of the fence
around the pasture. He measures
the fence
and finds
that he needs N (
1 ≤ N ≤
20,
000) planks
of wood, each having
some integer length Li (
1 ≤ Li ≤
50,
000) units. He
then purchases a single long board just long enough
to saw
into the N planks (i.e.,
whose length is the sum
of the lengths Li). FJ
is ignoring the "kerf",
the extra
length lost
to sawdust when a sawcut
is made; you should ignore
it, too.
FJ sadly realizes
that he doesn't own a saw
with which
to cut
the wood, so he mosies
over to Farmer Don's Farm
with this long board
and politely asks
if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw
but instead offers
to charge Farmer John
for each
of the N-
1 cuts
in the plank. The charge
to cut a piece
of wood
is exactly
equal to its length. Cutting a plank
of length 21 costs
21 cents.
Farmer Don
then lets Farmer John decide
the order
and locations
to cut
the plank. Help Farmer John determine
the minimum amount
of money he can spend
to create
the N planks. FJ knows
that he can cut
the board
in various different orders which will
result in different charges
since the resulting intermediate planks are
of different lengths.
Line
1: One
integer N,
the number of planks
Lines
2..N+
1: Each
line contains a single
integer describing
the length of a needed plank
Output
Line
1: One
integer:
the minimum amount
of money he must spend
to make N-
1 cuts
3
8
5
8
Sample Output
34
Solutions
本题使用贪心法
1. 找出数组中最小的二个。
2. 将最小的二个的长度加到总花费里。
3. 将这二个木板的长度消耗加到最小的当中木板当中
4. 将第二小的木板替换成当前最后一个木板
Source Code
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
int wood[
20001] = {
0};
for (
int i =
0; i < n; i++) {
cin >> wood[i];
}
long long pay =
0;
while (n >
1) {
int min1 =
0;
int min2 =
1;
if (wood[min1] > wood[min2]) {
swap(min1, min2);
}
for (
int i =
2; i < n; i++) {
if (wood[i] < wood[min1]) {
min2 = min1;
min1 = i;
}
else if (wood[i] < wood[min2]){
min2 = i;
}
}
long long t = wood[min1] + wood[min2];
pay += t;
if (min1 == n -
1) {
swap(min1, min2);
}
wood[min1] = t;
wood[min2] = wood[n -
1];
n--;
}
cout << pay << endl;
return 0;
}
类似于下面的代码，下面的代码复杂度高，但是易于理解
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int wood[
20001] = {
0};
for (
int i =
0; i < n; i++) {
cin >> wood[i];
}
long long pay =
0;
while (n >
1) {
sort(wood, wood + n);
pay += wood[min1] + wood[min2];
wood[min1] = wood[min1] + wood[min2];
wood[min2] = wood[n -
1];
n--;
}
cout << pay << endl;
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-35099.html
