## Saturday, November 28, 2015

### leetcode面试题2 抄书问题

leetcode面试题2 抄书问题
http://codevs.cn/problem/3162/

#### 解答

public int shortestTime(int[] pages, int k) {
int n = pages.length;
int[][] states = new int[k + 1][n + 1];
int[] sums = new int[n + 1];
sums[0] = 0;
sums[1] = pages[0];
states[1][1] = pages[0];
for (int i = 2; i <= n; i++) {
sums[i] = sums[i-1] + pages[i-1];
states[1][i] = sums[i];
//System.out.println(sums[i]);
}

for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
int minVal = Integer.MAX_VALUE;
for (int jj = 0; jj <= j; jj++){
int val = Math.max(states[i-1][j - jj] , sums[j] - sums[j-jj]);
if (val < minVal){
minVal = val;
}
}
states[i][j] = minVal;
}
}
return states[k][n];
}

http://www.cnblogs.com/cane/p/3894669.html
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 }```

http://blog.csdn.net/csyzcyj/article/details/17332821

```int M,K,a[MAX],min1=IMAX,max1=0,x[MAX],y[MAX],ans;
bool check(int x)
{
int sum=0,now=M;
for(int i=K;i>=1;i--)
{
sum=0;
while(sum+a[now]<=x && now>0)
{
sum+=a[now];
now--;
}
if(now==0)   return true;
}
return false;
}
void work()
{
int left=min1,right=max1;
while(left<right)
{
int middle=(left+right)/2;
if(check(middle))//说明最大值多了<即可能人没轮完就取完了>
right=middle;
else left=middle+1;//说明最大值少了<即还未取满就完了>
}
ans=left=right;
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
scanf("%d%d",&M,&K);
for(int i=1;i<=M;i++)
{
scanf("%d",&a[i]);
min1=min(a[i],min1);
max1+=abs(a[i]);
}
work();

int sum=0,now=M;
for(int i=K;i>=1;i--)
{
sum=0;
y[i]=now;
while(sum+a[now]<=ans && now>=i)
{
sum+=a[now];
now--;
}
x[i]=now+1;
}
for(int i=1;i<=K;i++)
printf("%d %d\n",x[i],y[i]);
return 0;
}```