题意
有两个软件需要开发 , 每个软件分为 \(m\) 部分 , 把这总共 \(2m\) 个任务分配给 \(n\) 个人 , 每个人完成软件1 , 软件2的一部分所消耗的时间分别为 \(a_i,b_i\) , 这 \(n\) 个人同时工作 , 完成的时间就是这 \(n\) 个人最慢的一个人完成他的所有任务的时间 . 通过分配任务 , 最小化完成时间 .
$n,m,a_i,b_i \le 100 $
题解
简单地构造分配方案是复杂的 . 因此转向二分答案 .
转化后因为已知时间限制 , 可以枚举每个人完成任务1的个数同时有对应最多能完成任务2的个数 .
问题转为平凡的背包 , 即 \(f_{i,j}\) 为考虑前 \(i\) 个人做 \(j\) 个任务1 , 能够完成的任务2的最多个数 . 复杂度 $O(n^3\log n) $ .
点击查看代码
#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define int long long
#define INF 0x7fffffff
#define INF64 1e18
using namespace std;
constexpr int N=105;
int n,m,a[N],b[N];
int f[N][N];
bool check(int t){
memset(f,0,sizeof f);
for(int i=0;i<=n;i++)
for(int j=1;j<=m;j++) f[i][j]=-1e18;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=j;k>=0;k--){
if(t-(j-k)*a[i]<0) break;
f[i][j]=max(f[i][j],f[i-1][k]+(t-(j-k)*a[i])/b[i]);
}
}
}
return f[n][m]>=m;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
int l=1,r=1e18,mid,res;
while(l<=r){
mid=l+r>>1;
if(check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
cout<<res;
}
具有典型的转化特征的题目 . 关键在于剪枝掉不合理的思路 (例如本题中贪心,构造方向都不可行 ) , 能显然地看出当前能够针对当前矛盾做出的转化 (比如本题的二分,状态设计 ) . 再从每个转化带来的有利影响 ( 典型地 , 二分答案将最优性问题变成的存在性问题 ) 出发 , 进一步解决 .
标签：二分,高手,题目,软件开发,int,mid,完成,软件,define From： https://www.cnblogs.com/youlv/p/18584855