社区讨论

求调!!!

P3124[USACO15OPEN] Trapped in the Haybales S参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhj9xqdk
此快照首次捕获于
2025/11/03 23:07
4 个月前
此快照最后确认于
2025/11/03 23:07
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

struct grass {
    long long s, p;
};

bool cmp(const grass& a, const grass& b) {
    return a.p < b.p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, b;
    cin >> n >> b;
    vector<grass> gra(n);
    for (int i = 0; i < n; ++i) {
        cin >> gra[i].s >> gra[i].p;
    }

    sort(gra.begin(), gra.end(), cmp);

    int k = -1;
    for (int i = 0; i < n - 1; ++i) {
        if (gra[i].p < b && b < gra[i+1].p) {
            k = i;
            break;
        }
    }
    if (k == -1) {
        cout << -1 << endl;
        return 0;
    }

    int l_min = k;
    int r_fixed = k + 1;
    while (l_min >= 0) {
        long long D = gra[r_fixed].p - gra[l_min].p;
        if (gra[l_min].s >= D) {
            break; 
        }
        l_min--;
    }

    int r_max = k + 1;
    int l_fixed = k; 
    while (r_max < n) {
        long long D = gra[r_max].p - gra[l_fixed].p;
        if (gra[r_max].s >= D) {
            break; 
        }
        r_max++; 
    }

    long long ans = LLONG_MAX;
    for (int l = l_min; l <= k; ++l) {
        if (l < 0) continue; 
        for (int r = k + 1; r <= r_max; ++r) {
            if (r >= n) continue; 
            long long D = gra[r].p - gra[l].p;
            if (gra[r].s >= D) {
                long long cost = max(0LL, D - gra[l].s);
                ans = min(ans, cost);
            }
            if (gra[l].s >= D) {
                long long cost = max(0LL, D - gra[r].s);
                ans = min(ans, cost);
            }
        }
    }

    if (ans == LLONG_MAX) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...