A Task Process hdu 3433

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3433

题目大意：有n个工人，来做A,B两种任务，其中A任务总共有x件，B任务总共有y件，给定每个工人干一件A任务和B任务所花费的时间。求这些人同时开始干这些任务，最少多长时间能把A、B两种任务都完成。

主题思路：分析本题可以发现，每个人分配的时间越长则每个人能做的任务也越多（可能相等，但是做的工作一定越多），也就是每个人分配的时间同最终完成任务的数量成正比例关系，即单调，所以这里可以二分时间。二分确定给每个人分配的时间。

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[60][210];
int a[55],b[55];
int n,x,y;

bool DP(int T){//T表示每个人都分得T时间
    int i,j,k;
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(i=1;i<=n;i++){
        if(dp[i][x]>=y)return true;//如果前i个人生产了x个a后能够生产的b的数量大于y，则T时间里可以完成两件任务
        for(j=0;j<=x;j++){//枚举前i-1个人完成的a任务数
            if(dp[i-1][j]!=-1){//前i-1个人完成能j个a任务，继续求解加上第i个人花费T时间的结果
                for(k=0;k<=min(T/a[i],x-j);k++){//枚举第i个人完成a任务的数量来求完成b任务的数量
                     int add=min((T-a[i]*k)/b[i],y-dp[i-1][j]);
                     dp[i][j+k]=max(dp[i-1][j]+add,dp[i][j+k]);
                }
            }
        }
    }
    if(dp[n][x]>=y){
        return true;
    }else{
        return false;
    }
}

int main(){
    int t;
    int ans;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        printf("Case %d: ",cas);
        scanf("%d%d%d",&n,&x,&y);
        ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        int l=0,r=a[1]*x+b[1]*y;//这里r可以这么设，因为不可能一个人完成所有任务会比大家一块完成快
        while(l<=r){
            int mid=(l+r)>>1;
            if(DP(mid)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}