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

发布时间:2023年12月30日

学习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
文章来源:https://blog.csdn.net/guolianggsta/article/details/135230492
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。