NC24228. [USACO 2015 Ope B]Trapped in the Haybales
描述
Each bale j has a size Sj and a distinct position Pj giving its location along the one-dimensional road. Bessie the cow starts at some location where there is no hay bale, and 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.
Bessie can escape to freedom if she can eventually break through either the leftmost or rightmost hay bale. Please compute the total area of the road consisting of real-valued starting positions from which Bessie cannot escape. For example, if Bessie cannot escape if she starts between hay bales at positions 1 and 5, then these encompass an area of size 4 from which she cannot escape.
输入描述
The first line of input contains N. Each of the next N lines describes a bale, and contains two integers giving its size and position, each in the range 1…109.
输出描述
Print a single integer, giving the area of the road from which Bessie cannot escape.
示例1
输入:
5 8 1 1 4 8 8 7 15 4 20
输出:
14
C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 444K, 提交时间: 2020-08-24 10:00:47
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int n;
struct node{int num,pos;}a[100005];
bool cmp(node x,node y){return x.pos<y.pos;}
int ans;
signed main()
{
n=read();
for(int i=1;i<=n;++i){a[i].num=read();a[i].pos=read();}
sort(a+1,a+n+1,cmp);
for(int i=1;i<n;++i)
{
int l=i,r=i+1;
while(l>=1&&r<=n)
{
bool bj=0;
if(a[l].num<a[r].pos-a[l].pos){--l;bj=1;}
if(a[r].num<a[r].pos-a[l].pos){++r;bj=1;}
if(!bj)break;
}
if(l>=1&&r<=n)ans+=a[i+1].pos-a[i].pos;
}
print(ans,'\n');
return 0;
}
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2020-09-07 19:16:35
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct vv{
int val,id;
}a[N];
bool f[N];//表示哪些区间可以直接到.
bool cmp(vv x,vv y)
{
return x.id<y.id;
}
int n;
bool ck(int x)
{
int l=x,r=x+1;
int s=a[r].id-a[l].id;
while(1<=l&&r<=n)
{
bool flag=false;
if(s>a[l].val)
{
l--;
flag=true;
if(f[l]) {f[x]=1;return true;}
s+=a[l+1].id-a[l].id;
}
if(s>a[r].val)
{
r++;
flag=true;
if(f[r]) {f[x]=1;return true;}
s+=a[r].id-a[r-1].id;
}
if(!flag) return false;
}
}
int main()
{
int ans=0;
scanf("%d",&n);
f[0]=1;f[n+1]=1;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].val,&a[i].id);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n-1;i++)
{
if(!ck(i)) ans+=a[i+1].id-a[i].id;
}
cout<<ans<<endl;
return 0;
}