题意分析

题目描述了一家软件开发公司需要同时完成两个项目，每个项目被划分为m个子项目。公司有n名员工，每个员工完成第一个项目的子项目需要x秒，完成第二个项目的子项目需要y秒。要求找出完成两个项目所需的最短时间，使得两个项目同时完成。 1.并行处理：不同子项目可以并行处理，但同一子项目不能并行。

2.同步完成：两个项目必须同时完成，不能一个提前完成。

3.时间最小化：目标是找到完成两个项目的最短时间。

解题思路

1. 问题建模 需要找到一个最小的时间T，使得：第一个项目的m个子项目可以在时间T内完成。第二个项目的m个子项目也可以在时间T内完成。两个项目同时完成。

2. 动态规划与二分搜索 二分搜索：由于我们需要最小化时间T，可以使用二分搜索来确定最小满足条件的时间。左边界（le）：0，右边界（ri）：最坏情况下，所有子项目由最慢的员工完成，即$maxx×m×2$。 对于每个候选时间T，检查是否可以在时间T内完成两个项目的m个子项目。 定义$dp[i][j]$表示前i个员工完成第一个项目的j个子项目时，最多能完成第二个项目的子项目数量。对于第i个员工，分配k个第一个项目的子项目，耗时$k×a[i]$。剩余时间T - k $×$a[i]可以完成$\frac{T - k \cdot a[i]}{b[i]}$个第二个项目的子项目。 $dp[i][j]=\max\left(dp[i][j],\ dp[i-1][j-k] + \frac{T - k \cdot a[i]}{b[i]}\right)$

3. 检查可行性 对于每个时间T，通过动态规划计算dp[n][m]：如果dp[n][m] >= m，说明可以在时间T内完成两个项目的m个子项目。否则，需要增加时间T。

代码实现

#include <stdio.h>
#include <string.h>
#include <vector>
#define N 105
#define INF 0x3f3f3f3f
using namespace std;

int n,m,maxx;
int a[N],b[N];
int dp[N][N];

int ok(int tim)
{
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<=m;i++)
		if(i*a[1]<=tim)
			dp[1][i]=(tim-i*a[1])/b[1];
	else break;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
			for(int k=0;k<=j&&a[i]*k<=tim;k++)
				if(dp[i-1][j-k]!=-1)
					dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(tim-k*a[i])/b[i]);
	}
	return  dp[n][m]>=m;
}

void re(void)
{
	maxx=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		maxx=max(a[i],maxx);
		maxx=max(b[i],maxx);
	}
}

void run(void)
{
	int le=0,ri=maxx*m*2,mid;
	while(mid=(le+ri)/2,le<ri)
	{
		if(ok(mid))ri=mid;
		else           le=mid+1;
	}
	printf("%d\n",ri);
}

int main()
{
	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		re();
		run();
	}
	return 0;
}