社区讨论
求调!!!
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 条回复,欢迎继续交流。
正在加载回复...