题解
每一个任务都有一个最小起点能力值,和通过任务后获得的能力值,我们从最小起点开始遍历,如果遍历到某一点累加的能力值+最小起点能力值够不到当前任务的最小能力值,我们把最小起点向右移动直至够到当前任务的最小能力值。
code
#include<bits/stdc++.h>
using namespace std;
struct node
{
int pos,len;
bool operator<(const node &b){return b.pos>pos;}
};
int a[100005];
int main()
{
int t;
cin>>t;
while(t--)
{
vector<node> q;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
int start=0;
for(int j=1;j<=k;j++)
{
cin>>a[j];
start=max(start,a[j]-j+2);//干掉前i-1个怪物后会获得i-1的能力值,还要大于当前怪物的能力值:start+i-1>b[i] -> start+i-1-1>=b[i] 要让start尽可能小
}
q.push_back({start,k});
}
sort(q.begin(),q.end());
int start=q[0].pos,far=start+q[0].len;
for(int i=1;i<q.size();i++)
{
if(q[i].pos<=far)
{
far+=q[i].len;
}
else
{
start+=q[i].pos-far;
far+=q[i].pos-far;
far+=q[i].len;
}
}
cout<<start<<endl;
}
return 0;
}
标签:当前任务,int,最小,Deep,Down,start,Below,能力,起点
From: https://www.cnblogs.com/pure4knowledge/p/18124864