CF1561C Deep Down Below
时间限制：\(2s\) | 空间限制：\(1000MB\)
题面
题面翻译
\(T\) 组数据，每次给定 \(n\) 个任务，第 \(i\) 个任务给定 \(k_i\) 个怪物，每个怪物有一个能力值 \(a_{i,j}\) 你要按顺序把这 \(k_i\) 个怪物杀死，你能杀死一个怪物当且仅当你的能力值严格大于怪物的能力值，杀死一个怪物后，你的能力值将会 \(+1\)。
你可以按任意顺序完成这 \(n\) 个任务，你需要确定最小的初始能力值。
\(T\leq 10^5,n\leq 10^5,k_i\leq10^5,\sum k_i\leq 10^5,a_{i,j}\leq 10^9\)。
样例输入 #1
2
1
1 42
2
3 10 15 8
2 12 11
样例输出 #1
43
13
题解
看到这题，第一反应肯定是贪心。很明显，策略就是每次进入最大值最小的序列（山洞），击杀并获得加成
但是这道题的武力值是实时变化的，就可以进行一个预处理：
假设我要进入这个山洞：（第一行是山洞中怪物的个数）
5
10 11 23 12 17
假设当前的武力值为\(k\)，那么打到第\(i\)个怪物时，武力值就会变为\(k+i-1\)（假定英雄武力值足够大，能够达到\(i\)）
换句话说，如果英雄武力值一直为\(k\)，那么第\(i\)个怪物在遇到英雄时，他的防御力就需要减掉一个\(i-1\)
这样我们就解决了山洞中武力值变化的问题了。
这时，我们又会发现一个问题，当样例是这样时：
8
6 22 11 16 12 12 16
1 6
4 19 1 15 22
10 24 11 6 7 11 15 20 22 2 6
10 5 3 6 1 12 24 20 4 1 23
6 10 3 24 1 24 8
1 19
7 8 23 4 5 7 20 18
按照我们的思路，肯定是先去第\(2\)个，武力值为\(7\)，再去第\(5\)个，武力值为\(20\)
可是会发现，最优解是\(19\)，并不是\(20\)，所以我们的思路会有一点漏洞
那该怎么改进呢？可以想到，如果从前往后找不行，那就试试从后往前找
当遇到一个洞穴，想要顺利通过的值是可以被求出来的，这个值有两种方法得到：
- 从一开始就是这个值
- 是在上一个（所需武力值小于当前的）一个洞穴中通过加分得到的
很明显，2是比1要更有的，所以每次判断，当前武力值能否从上一个相加得来，可以的话就加，不能就将初始值所需的武力值
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
int n,ans,now;
struct cave
{
int size;
int maxn;
}a[Maxn];
bool cmp(cave x,cave y)
{
return x.maxn<y.maxn;
}
void run()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].size;a[i].maxn=0;
for(int j=1;j<=a[i].size;j++)
{
int t;
cin>>t;
a[i].maxn=max(a[i].maxn,t-j+1);
}
}
sort(a+1,a+1+n,cmp);
ans=a[n].maxn+1;
for(int i=n;i>=2;i--)
{
// cout<<a[i-1].size<<" "<<a[i-1].maxn<<" "<<ans<<endl;
if(ans-a[i-1].size<=a[i-1].maxn+1) ans=a[i-1].maxn+1;
else ans-=a[i-1].size;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) run();
}