USACO 2023年12月铜组 FARMER JOHN ACTUALLY FARMS（数学 思维）

admin管理员组

文章数量:1530238

第三题：FARMER JOHN ACTUALLY FARMS

标签：思维、数学
题意：给定 n n n个数字初始值 h i h_i hi​，第 i i i个数字每天会增加 a i a_i ai​，再给出包含 0 0 0到 n − 1 n-1 n−1之间所有数字的数组 t i t_i ti​，求满足 对于第 i i i 个数字，正好有 t i t_i ti​ 个比它更大的数字 的最少天数。

题解：题目要求对于对于第 i i i个数字，正好有 t i t_i ti​ 个比它更大的数字，那么我们肯定得从最小（ t i = 0 t_i=0 ti​=0）的数开始，然后第二小的数（ t i = 1 t_i=1 ti​=1）…，在这个过程中，不断地让相邻的两个数看看能不能在初始值为 h i h_i hi​，每天增量为 a i a_i ai​的情况下满足后一个数大于前一个数，在这个过程中不断地去求这个天数的最大值。

所以一开始我们得去做个映射：第 t i t_i ti​大的数是输入的第 i i i个数。
然后在第 1 1 1小的数、第 2 2 2小的数、第 3 3 3小的数… 的过程中，看看两个数是否不符合当前数大于前一个数不符合，且在当前数增量大于前一个数增量的情况下，去求需要增量增加的天数，因为需要满足所有的，所以维护这边天数的最大值。

需要注意的是，想让结果是大于的情况，可以给被除数（数字初始值只差 + 1 +1 +1），再进行处理。
最后再判定一下，修改完之后的序列是否满足题目中要求的顺序，不满足输出 − 1 -1 −1。
代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2e5 + 10;
ll h[N], a[N], t[N], f[N];

int main() {
    ll T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> h[i];
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) {
            cin >> t[i];
            f[t[i]] = i;
        }
        ll ans = 0;
        for (int i = 1; i < n; i++) {
            if (a[f[i-1]] > a[f[i]] && h[f[i-1]] < h[f[i]]) {
                ll k = (h[f[i]] - h[f[i-1]] + 1) / (a[f[i - 1]] - a[f[i]]);
                if ((h[f[i]] - h[f[i-1]] + 1) % (a[f[i - 1]] - a[f[i]])) k++;
                ans = max(ans, k);
            }
        }
        for (int i = 1; i <= n; i++) h[i] += ans * a[i];
        bool flag = 1;
        for (int i = 1; i < n; i++) {
            if (h[f[i-1]] <= h[f[i]]) flag = 0;
        }
        if (flag) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}

本文标签： 思维数学USACO月铜组FARMS