F题题解
赛时想了个大模拟写法,写红温了,好在赛后对拍找到了错误地方最终调出来了,也算是证明了思路的正确性。
以下做法并非官方题解中的 做法:
每个 可以表示为
的形式,为了方便我们将其表示为
的形式,后续我们的
其实都表示的是
。
拿到一个 的
有两种方式:
- 如果存在一个
其为
,且
,则我们可以直接拿到
这个
。
- 如果存在一个
其为
,且有
, 如果我们能拿到
这个offer,则我们就可以拿到
这个
,问题便递归的转换成了我们如何拿到
这个
。该递归的出口是采用第一种方式拿到
。
如何决策最优?即对于第二种方式若存在多个满足条件的 ,我们更容易拿到哪个
的
? 最优的方式应该是我们拿
最小的那个,因为这样更容易存在一个
(
),我们直接拿到薪金
,然后换取
,进而换取
。
为了快速地找到所有符合条件的 ,我们需要将所有
按照
从小到大排序,然后我们便可以使用二分来快速找到符合条件的区间,我们还要使用诸如线段树的数据结构来快速查询一个区间的最小值(即找到最小的
,以及其对应的
)。
所以我的具体做法是,将所有 按照
从小到大排序,按照排序后
的顺序建立线段树,线段树中每个节点存储
的值及其对应的
编号,然后按照
的倒序来调用
函数进而递归地确定当前
是否可以拿到,同时使用记忆化搜索来降低重复搜索。
时间复杂度 ,详细细节见我的屎山代码:
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int mod=1e9+7;
const int N=2e5+10;
int st[N];
struct node1
{
int a,b;
bool operator < (const node1&h) const
{
if(b!=h.b) return b<h.b;
return a>h.a;
}
}e[N];
struct node
{
int l,r;
PII v;
}tr[4*N];
int n;
void pushup(int u)
{
tr[u].v=min(tr[u << 1].v,tr[u << 1 | 1].v);
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,{e[l].a,l}};
else
{
tr[u]={l,r,{0,0}};
int mid=l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)
{
if(tr[u].l==tr[u].r && tr[u].r==x) tr[u].v.x=v;
else
{
int mid=tr[u].l + tr[u].r >> 1;
if(x<=mid) modify(u << 1,x,v);
else modify(u << 1 | 1,x,v);
pushup(u);
}
}
PII query(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r <=r) return tr[u].v;
else
{
int res=0;
int mid=tr[u].l + tr[u].r >> 1;
PII mi={1e18,0};
if(l<=mid) mi=min(mi,query(u << 1,l,r));
if(r>mid) mi=min(mi,query(u << 1 | 1,l,r));
return mi;
}
}
multiset<int> s;
int ask(int u)
{
if(st[u]!=0) return st[u];
int x=e[u].a;
if(s.size() && *s.rbegin()>=x)
{
return st[u]=1;
}
if(s.size()==0) return st[u]=-1;
int l=1,r=u-1;
while(l<r)
{
int mid=(l+r)/2;
if(e[mid].b<e[u].a) l=mid+1;
else r=mid;
}
if(l>=1 && l<=u-1 && e[l].b>=e[u].a)
{
PII mi=query(1,l,u-1);
s.erase(s.find(mi.x));
modify(1,mi.y,1e18);
int ans=ask(mi.y);
if(ans==1)
{
return st[u]=1;
}
}
return st[u]=-1;
}
void solve()
{
s.clear();
scanf("%lld",&n);
int ma=0;
for(int i=1;i<=n;i++)
{
st[i]=0;
scanf("%lld%lld",&e[i].a,&e[i].b);
e[i].b+=e[i].a;
ma=max(ma,e[i].a);
s.insert(e[i].a);
}
sort(e+1,e+n+1);
build(1,1,n);
int ma1=0;
for(int i=n;i>=1;i--)
{
if(ma1>=e[i].a)
{
ma=max(ma,e[i].b);
st[i]=1;
}
ma1=max(ma1,e[i].a);
if(st[i]==0)
{
s.erase(s.find(e[i].a));
modify(1,i,1e18);
ask(i);
}
}
for(int i=1;i<=n;i++)
{
if(st[i]==1) ma=max(ma,e[i].b);
}
printf("%lld\n",ma);
}
signed main()
{
int t=1;
cin >> t;
while(t--) solve();
}