首页 > 代码库 > POJ3253-Fence Repair

POJ3253-Fence Repair

2024-07-25 23:03:13   221人阅读

将一块很长的木板切割成N块，长度分别为L1、L2、…、LN。每次切割需要的开销为当前木板的长度。求出将木板切割完最小开销是多少。

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5  6 #define MAX_N 30000 7  8 int N, L[MAX_N]; 9 10 11 int solve()12 {13     long long ans = 0;14     //直到计算到木板为1块为止15     while (N > 1)16     {17         //求出最短板mii1和次短板mii218         int mii1 = 0, mii2 = 1;19         if (L[mii1] > L[mii2]) swap(mii1, mii2);20 21         for (int i = 2; i < N; i++)22         {23             if (L[i] < L[mii1])24             {25                 mii2 = mii1;26                 mii1 = i;27             }28             else if (L[i] < L[mii2])29             {30                 mii2 = i;31             }32         }33 34         //将两块木板合并35         int t = L[mii1] + L[mii2];36         ans += t;37 38         if (mii1 == N-1) swap(mii1, mii2);39         L[mii1] = t;40         L[mii2] = L[N-1];41         N--;42     }43 44     printf("%lld\n", ans);45 }46 47 int main()48 {49     cin >> N;50     for (int i = 0; i < N; i++)51         cin >> L[i];52     solve();53     return 0;54 }

 

POJ3253-Fence Repair


联系
我们