USACO历年青铜组真题解析 | 2023年12月Farmer John Actually Farms

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考青铜组别比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO历年青铜组真题解析 | 汇总_usaco竞赛青铜组题-CSDN博客

【题目描述】

农夫约(FJ)在他的农场上种植了N (1≤N≤2?10^5)株芦笋！但是一些植物有遗传差异，所以有些植物会比其他植物生长得更快。第i株植物的初始高度是hi英寸，每天过后，第ii株植物会生长ai英寸。

FJ会更偏爱某些植物，他希望某些特定的植物比其他植物要高。他给了你一个数组t1,…,tN，包含了从0到N?1的所有不同整数值，并且他希望对于第i株植物，有ti株植物的高度比它高。找出满足FJ要求的最少天数，或者确定这是不可能的。

【输入】

每个测试用例包含T个子测试用例。输入的第一行包含整数T(1≤T≤10)。以下是T个子测试用例。

每个子测试用例的第一行包含一个整数N。

第二行由N个整数hi(1≤hi≤10^9)组成，表示第i株芦笋的初始高度。

第二行由N个整数ai(1≤hi≤10^9)组成，表示每天第i株芦笋的生长高度。

第四行包括N个不同整数ti，这是FJ给你提供的数组。

保证所有测试用例中N的总和不超过2?10^5。

【输出】

输出T行，每行表示对应测试用例的答案。如果无法实现，则输出?1。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

【输入样例】

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

【输出样例】

0
3
2
5
-1
-1

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int T, n;
struct node {
    long long h, a, t;
}p[200005];
bool cmp (node x, node y){
    return x.t<y.t;
}
int main()
{
    cin >> T;  // 输入T
    while (T--) {  // 遍历T次询问
        cin >> n;  // 输入n
        for (int i=1; i<=n; i++) cin >> p[i].h;  // 使用结构体数组，记录每个植物的h、a和t
        for (int i=1; i<=n; i++) cin >> p[i].a;
        for (int i=1; i<=n; i++) cin >> p[i].t;
        if (n==1) {  // 如果n==1特判，输出0
            cout << 0 << endl;
            continue;
        }
        int minn=1e9, maxn=-1e9;  // 定义满足条件的最大值和最小值
        sort(p+1, p+n+1, cmp);  // 按照t从小到大方式排序
        int mark=0;  // 定义标记位
        for (int i=1; i<n; i++) {  // 遍历n-1个植物
            int a=p[i].h, b=p[i].a, c=p[i+1].h, d=p[i+1].a;  // 定义变量简化代码长度
            if (b==d) {  // 当b==d时
                if (a<=c) {  // 如果a小于等于c，永远无法追上，输出-1
                    cout << -1 << endl;
                    mark = 1;
                    break;
                } else {  // 否则，只需0天就可以满足
                    maxn = max(maxn, 0);
                }
            }
            if (b>d) {  // 当b>d时
                if (a<=c) {  // 如果a小于等于c，则在某天之后就一直超越
                    int x = (c-a)/(b-d)+1;  // 相减后相除的结果是相等的情况，还需要再加1
                    maxn = max(maxn, x);      
                } else {  // 否则，只需0天就可以满足
                    maxn = max(maxn, 0);
                }
            }
            if (b<d) {  // 当b<d时
                if (a<=c) {  // 如果a小于等于c，永远无法追上，输出-1
                    cout << -1 << endl;
                    mark=1;
                    break;
                } else {
                    int x = (a-c-1)/(d-b);  // 否则开始超越，但到某天后就不再满足
                    maxn = max(maxn, 0);
                    minn = min(minn, x);  // 记录该minn
                }
            }
        }
        if (mark==1) continue;  
        if (maxn>minn) {  // 要求maxn>minn，即满足条件maxn < x < minn，才有结果输出，否则输出-1
            cout << -1 << endl;
            continue;
        } else {
            cout << maxn << endl;
        }
    }
    return 0;
}

【运行结果】

6
1
10
1
0
0
2
7 3
8 10
1 0
3
2
3 6
10 8
0 1
2
2
7 3
8 9
1 0
5
2
7 7
8 8
0 1
-1
2
7 3
8 8
1 0
-1