自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 23:15:42，当前版本为作者最后更新于2025-05-10 22:42:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

临晚再写一篇。

思路

很明显，这是一道拓扑排序题，这里大家可能不知道拓扑排序，那么到这儿了解一下。
那么这道题怎么做呢？我们可以用拓扑排序找到每一个点如果要击落那么需要花费的注意力，找到编号最大的即可。
具体来说，就是用队列来存储可以选择的数，然后赋值。值得注意的是，可能有的球永远打不下来，如图：

所以最开始要赋一个极大值，以免永远打不下来的被打下来了。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
queue<int> q;
int a[200005],f[200005],b[200005];
vector<int> g[200005];
signed main(){
	memset(b,0x3f,sizeof(b));
	int n,w;
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>f[i];
		if(f[i]==-1){
			q.push(i);
			b[i]=a[i];
		}
		else{
			g[f[i]].push_back(i);
		}
	}
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(auto i:g[t]){
			if(f[i]!=-1){
				b[i]=b[t]+a[i];
				f[i]=-1;
				q.push(i);
			}
		}
	}
	for(int i=n;i>=1;i--){
		if(w>=b[i]){
			cout<<i;
			return 0;
		}
	}
	cout<<-1;
    return 0;
}