秋招复盘：广联达笔试

第一题 自己就过了18%,在牛客上学习了别人方法

dp+2分查找

#include<bits/stdc++.h>

using namespace std;

int bitsearch(vector<vector<int>> &nums, int right, int start)
{
	// 2分查找  找到小于start的第一个nums[j]中的值 
	int left = 0;
	while(left <= right)
	{
		int mid = left + (right-left)/2;
		if(nums[mid][1]<=start)
		{
			left = mid +1;
		} else{
			right = mid -1;
		}
	}
	return right;
}
int main()
{
	int n;
	cin >> n;
	vector<vector<int>> nums(n, vector<int>(3));
	for(int i=0; i<n; i++)
	{
		cin >> nums[i][0];
	}
	for(int i=0; i<n; i++)
	{
		cin >> nums[i][1];
		nums[i][1] += nums[i][0]; // 将start_time + nums[i][1] 计算出 end_time 
	}
	for(int i=0; i<n; i++)
	{
		cin >> nums[i][2]; 
	}
	// 排序 按照第二个维度从小到达排序 
    sort(nums.begin(), nums.end(), [](const vector<int>& v1, const vector<int>& v2) {
    return v1[1] < v2[1];
    });
	long dp[n+1];
	// dp 数组 
	// dp[i] 表示第i个订单时能获得最大报酬 
	dp[0]=0; // 第0个订单是获得最大报酬为0 
	for(int i=1; i<=n; i++){ // 从1开始遍历到n 表示1到n个订单 
		// 对于第i个订单如果不接单，则第i个订单时获得的最大报酬和第i-1个订单一样 
		dp[i] = dp[i-1];
		// 如果接单，需要找到接该单前能完成的第j个订单 ，根据二分查找，找到小于第i个订单的start_time  nums[i-1][0];
		int j = bitsearch(nums, i-1, nums[i-1][0]); 
		
		// 第 j个订单完成后对应的值为 dp[j+1],加上第i个订单的值nums[i-1][2] 
		long jiedan =  dp[j+1] + nums[i-1][2];
		dp[i] = max(dp[i], jiedan);  // 选择最大的 
	}
	cout << dp[n] << endl; 
} 
/*
测试用例
5 
1 3 6 7 11
4 3 4 3 9
2 5 5 3 4
输出
14 
*/