返回信息流给定n组任务和时间t，要求在t时间内选择两个任务，使得两任务的value之和最大。
输入首先会给你一个time数组，表示第i个任务要花费的时间，time按照花费时间从小到大顺序给出。
其次有一个value数组，表示第i个任务的价值。
两者一一对应表示每一个任务的时间和价值。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #101004同步于 2023/4/24
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
字节面试一道题 暴力超时 我太菜求个ON思路
chance21
2023/4/24镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
i遍历0到n-1，记录maxvalue[i]为value[0到i]的最大值，那么对于取任务i为第2个任务时，第1个任务可以在logn复杂度内找到。整体下来复杂度在nlogn
```python
n = int(raw_input())
T = int(raw_input())
ts = map(int, raw_input().split())
vs = map(int, raw_input().split())
tasks1 = sorted(zip(ts, vs), key=lambda (t, v): (t, -v))
tasks2 = tasks1[:]
for i in xrange(1, n):
tasks1[i][1] = max(tasks1[i][1], tasks1[i - 1][1])
res = 0
p, q = 0, n - 1
while p < q and q > 0:
t2 = tasks2[q][0]
v2 = tasks2[q][1]
while p < q and tasks1[p][0] + t2 < T:
p += 1
res = max(res, tasks1[p][1] + v2)
q -= 1
p = min(p, q - 1)
print res
```
瞎写的，对错难料（
你这个思路再进一步就有O(n)的解法了: 第1个任务可以在1复杂度内找到
双指针扫time数组，p=1, q=n，保持time[p]+time[q]是选中q的情况下，p能取的最大值。这个情况下的最大收益就是value[q]+max{value[1..p]}。q从n开始减小，p是只增不减的，就可以把logn干掉。
```
p = 1
q = n
while (p < q):
while (p < q && time[p]+time[q] <= T):
ans = max(ans, value[q]+maxvalue[p])
p++
q--
return ans
```
进一步，因为p只增不减，maxvalue[]数组也可以干掉，只用一个max_value_on_the_left：
```
p = 1
q = n
max_value_on_the_left = 0
while (p < q):
while (p < q && time[p]+time[q] <= T):
max_value_on_the_left = max(max_value_on_the_left, value[p])
ans = max(ans, value[q] + max_value_on_the_left)
p++
q--
return ans
```
【 在 intmain 的大作中提到: 】
: i遍历0到n-1，记录maxvalue[i]为value[0到i]的最大值，那么对于取任务i为第2个任务时，第1个任务可以在logn复杂度内找到。整体下来复杂度在nlogn
仰慕上古神牛
【 在 wolf5x 的大作中提到: 】
: [md]
: 你这个思路再进一步就有O(n)的解法了: 第1个任务可以在1复杂度内找到
: 双指针扫time数组，p=1, q=n，保持time[p]+time[q]是选中q的情况下，p能取的最大值。这个情况下的最大收益就是value[q]+max{value[1..p]}。q从n开始减小，p是只增不减的，就可以把logn干掉。
: ...................