NC24224. [USACO 2015 Ope S]Trapped in the Haybales
描述
Bessie the cow can move around freely along the road, even up to the position at which a bale is located, but she cannot cross through this position. As an exception, if she runs in the same direction for D units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than D. Of course, after doing this, she might open up more space to allow her to make a run at other hay bales, eliminating them as well.
FJ is currently re-painting his house and his barn, and wants to make sure Bessie cannot reach either one (cows and fresh paint do not make a good combination!) Accordingly, FJ wants to make sure Bessie never breaks through the leftmost or rightmost hay bale, so she stays effectively trapped within the hay bales. FJ has the ability to add hay to a single bale of his choosing to help keep Bessie trapped. Please help him determine the minimum amount of extra size he needs to add to some bale to ensure Bessie stays trapped.
输入描述
The first line of input contains N as well as Bessie's initial position B. Each of the next N lines describes a bale, and contains two integers giving its size and position. All sizes and positions are in the range 1…109.
输出描述
Print a single integer, giving the minimum amount of hay FJ needs to add to prevent Bessie from escaping. Print -1 if it is impossible to prevent Bessie's escape.
示例1
输入:
5 7 8 1 1 4 3 8 12 15 20 20
输出:
4
C++11(clang++ 3.9) 解法, 执行用时: 46ms, 内存消耗: 1628K, 提交时间: 2020-03-14 21:01:57
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,ans;
struct bale
{
int x,d;
}s[maxn];
int f[maxn];
set<int> s1,s2;
bool cmp(bale a,bale b)
{
return a.x<b.x;
}
int main()
{
scanf("%d%d",&n,&m);
ans=1<<30;
int i,j,l,r,mid;
for(i=1;i<=n;i++) scanf("%d%d",&s[i].d,&s[i].x);
s[++n].x=m;
sort(s+1,s+n+1,cmp);
for(i=1;i<=n;i++)
if(s[i].x==m)
{
m=i;
break;
}
f[m]=-1<<30;
for(i=m-1;i>=1;i--) f[i]=max(f[i+1],s[i].x+s[i].d);
for(i=m+1;i<=n;i++) f[i]=max(f[i-1],s[i].d-s[i].x);
for(i=m+1;i<=n;i++)
{
l=1,r=m;
while(l<r)
{
mid=l+r>>1;
if(s[i].x-s[mid].x<=s[i].d) r=mid;
else l=mid+1;
}
if(r<m) ans=min(ans,max(0,s[i].x-f[r]));
}
for(i=1;i<m;i++)
{
l=m+1,r=n+1;
while(l<r)
{
mid=l+r>>1;
if(s[mid].x-s[i].x<=s[i].d) l=mid+1;
else r=mid;
}
if(l>m+1) ans=min(ans,max(0,-s[i].x-f[l-1]));
}
if(ans==1<<30) printf("-1");
else printf("%d",ans);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 1180K, 提交时间: 2020-08-23 10:11:03
#include "bits/stdc++.h"
using namespace std;
#define INF 1000000010
int main() {
int N, B;
cin >> N >> B;
vector<pair<int, int> > A(N);
for (int i = 0; i < N; i++) {
cin >> A[i].second >> A[i].first;
}
sort(A.begin(), A.end());
int result = INF;
int sp = lower_bound(A.begin(), A.end(), make_pair(B, 0)) - A.begin();
int j = sp;
for (int i = sp - 1; i >= 0; i--) {
while (j < N && A[j].first <= A[i].first + A[i].second) {
result = min(result, A[j].first - A[i].first - A[j].second);
j++;
}
}
j = sp - 1;
for (int i = sp; i < N; i++) {
while (j >= 0 && A[i].first - A[i].second <= A[j].first) {
result = min(result, A[i].first - A[j].first - A[j].second);
j--;
}
}
if (result == INF) {
cout << -1 << endl;
} else {
cout << max(result, 0) << endl;
}
return 0;
}