首页 > 代码库 > 九章算法--分配抄书员

九章算法--分配抄书员

2024-07-16 02:33:50   221人阅读

思路：

（1）最常见的思路就是dp：状态表示为dp[i][j]，表示前j个人抄i本书最少时间；dp[i][j] = min(max(dp[k][j-1],sum(k+1,i))) (j<=k<i)；

解释一下min,max操作，由于抄书是并行，所以就是取所有人时间里的最大值

（2）二分+贪心：我自己一开始的思路是总和除以人数，然后贪心，但是这样可能不是最优解。但是我们可以计算每个人最大和最小抄书的时间，然后二分搜索这个时间即可。

下面代码是DP：但是没有考虑边界情况只是写来熟悉算法流程。

 1 #include <iostream> 2 #include <string> 3 #include <memory.h> 4 #include <vector> 5 #include <sstream> 6 #include <math.h> 7 #include <climits> 8 #include <algorithm> 9 using namespace std;10 11 //dp：f[i][j]表示前i本书由j个抄书员来抄的最少时间，12 //f[i][j] = min(f[x][j-1]+sum(x+1,i))(j<=x<=i)13 ///sum[i][j]表示抄写第i到第j本书需要的时间14 vector<int> book;15 int dp[100][100];16 int sum[100][100];17 int fun(int n,int m)18 {19     int i,j,k;20     int mintime=INT_MIN;21     22     for(i = 0 ; i < n ; ++i)23     {24         for(j = i ; j < m ;++j)25         {26             for(k = i ; k <= j ; ++k)27             {28                 sum[i][j]+=book[k];29             }30         }31     }32     for(i = 1 ; i <= n ; ++i)33         dp[i][1] = sum[0][i-1];34     for(j = 2 ; j <= m ; ++j)35     {36         for(i = j ; i <= n ; ++i)37         {38             dp[i][j]= INT_MAX;39             for(k = j ; k <= i ; ++k)40             {41                 mintime = max(dp[k][j-1],sum[k][i-1]);42                 dp[i][j] = min(dp[i][j],mintime);43             }44         }45     }46     return dp[n][m];47 }48 49 int main()50 {51 52     return 0;53 }

 


联系
我们