E2-A 此处即是勇者试炼之殿堂

题目描述

小 AA 正在勇闯算法分析与设计！

小 AA 需要先挑战 nn 周的比赛才能挑战期末考试。第$ i$ 周（1≤i≤n）（1≤i≤n）有一场上机赛和一场练习赛，难度值分别为 Ci,EiC_i,E_i。

小 AA 初始的能力值为 AA，每一周小 AA 可以选择两场比赛中至少一场 AKAK。如果小 AA 的能力值不小于比赛的难度值，那么小 AA 能顺利 AKAK 比赛并通过挑战。在一周所有比赛结束后，小 AA 的能力值可以得到相当于 AKAK 比赛难度值之和的提升。如果小 AA 这一周无法 AKAK 任何一场比赛，那么小$ A$ 这一周挑战失败，无法继续接下来的挑战。

小 AA 需要你帮忙计算，他最多能通过多少周的挑战。

输入

第一行，一个正整数 T（1≤T≤100）T（1≤T≤100），表示数据组数。

对于每组数据：

第一行，两个整数 n,A（1≤n≤104,−109≤A≤109）n,A（1≤n≤10^4,−10^9≤A≤10^9），分别表示比赛周数与小 A 的初始能力值。

第二行，nn 个整数 C1,C2,…,Cn（−109≤Ci≤109）C_1,C_2,…,C_n（−10^9≤C_i≤10^9），表示每一周上机赛的难度值。

第三行，nn 个整数 E1,E2,…,En（−109≤Ei≤109）E_1,E_2,…,E_n（−10_9≤E_i≤10_9），表示每一周练习赛的难度值。

输出

对于每组数据：输出一行，一个整数，表示答案。

题目分析

小AA每周能力值AA与CiC_i和EiE_i的大小情况只有三种，由此可以分类讨论：

  1. A<min(Ci,Ei)A<min(C_i,E_i)，此时结束比赛输出当前周数；
  2. min(Ci,Ei)<=A<max(Ci,Ei)min(C_i,E_i)<=A<max(C_i,E_i)，此时直接加上min(Ci,Ei)min(C_i,E_i)即可；
  3. A>=max(Ci,Ei)A>=max(C_i,E_i)，因为CiC_i和EiE_i有可能小于00所以AA在加上max(Ci,Ei)max(C_i,E_i)后需要判断min(Ci,Ei)min(C_i,E_i)是否小于零；

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>

long long c[111000];
long long e[111000];

long long int max(long long int a, long long int b)
{
    return a > b ? a : b;
}
long long int min(long long int a, long long int b)
{
    return a < b ? a : b;
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        int n;
        long long A = 0;
        int ans = 0;
        scanf("%d%lld", &n, &A);

        for (int j = 0; j < n; j++)
        {
            scanf("%lld", &c[j]);
        }
        int flag = 0;
        for (int j = 0; j < n; j++)
        {
            long long int improve = 0;
            scanf("%lld", &e[j]);
            if (flag == 1)
            {
                continue;
            }
            ans = j;
            if (A < c[j] && A < e[j])
            {
                flag = 1;
                continue;
            }
            if (A >= max(c[j], e[j]))
            {
                improve = min(c[j], e[j])<0?max(c[j], e[j]):c[j]+e[j];
            }
            else
            {
                improve = min(c[j], e[j]);
            }

            A += 1LL * improve;
        }

        if ((A >= c[n - 1] || A >= e[n - 1]) && ans == n - 1)
        {
            ans = n;
        }
        printf("%d\n", ans);
    }

    return 0;
}