C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 2804K, 提交时间: 2020-08-31 01:13:33

#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;
}

C++11(clang++ 3.9) 解法, 执行用时: 49ms, 内存消耗: 1256K, 提交时间: 2020-08-30 20:00:36

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+5;

struct P{
    int s,p;
    bool operator<(const P&t)const{return p<t.p;}
}a[maxn];
int n;
bool vis[maxn];
bool solve(int l,int r)
{
    int d=a[r].p-a[l].p;
    while(1)
    {
        if(l<1||r>n||vis[l]||vis[r-1])return 1;
        if(a[l].s>=d&&a[r].s>=d)return 0;
        if(a[l].s<d)l--,d=a[r].p-a[l].p;
        if(a[r].s<d)r++,d=a[r].p-a[l].p;
    }
}
int main()
{
    int res=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].s,&a[i].p);
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++)
        if(!solve(i,i+1))res+=a[i+1].p-a[i].p;
        else vis[i]=1;
    printf("%d\n",res);
}

pypy3(pypy3.6.1) 解法, 执行用时: 694ms, 内存消耗: 39424K, 提交时间: 2020-08-31 23:52:17

#!/usr/bin/env python3
#
# Trapped in the Haybales (Gold)
#
import sys, os

def read_int(): return int(input())
def read_ints(): return list(map(int, input().split()))

n = read_int()
a = sorted([read_ints() for _ in range(n)], key=lambda x: x[1])
f = [False] * (n + 1)
f[0] = f[n] = True

def check(p):
	d = a[p][1] - a[p - 1][1]
	l, r = p, p
	while l > 0 and r < n:
		ok = False
		if d > a[l - 1][0]:
			ok = True
			l -= 1
			if f[l]:
				f[p] = True
				return True
			d += a[l][1] - a[l - 1][1]
		if d > a[r][0]:
			ok = True
			r += 1
			if f[r]:
				f[p] = True
				return True
			d += a[r][1] - a[r - 1][1]
		if not ok: break
	return False

ans = 0
for i in range(1, n):
	if not check(i):
		ans += a[i][1] - a[i - 1][1]
print(ans)