#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100000+5;
int T;
//d(u) 第u个人至少需要多少工人
vector<int> sons[maxn];
int dp(int u)
{int k=sons[u].size();if(!k) return 1; // 工人 vector<int> d;for(int i=0;i<k;i++)d.push_back(dp(sons[u][i])); //每一个直系下属递交的需要多少工人数sort(d.begin(),d.end()); int c=ceil(k*T/100.0); //直系下属至少多少人递交 int ans=0; for(int i=0;i<c;i++) ans+=d[i]; //取需要工人最少的前c个直系下属的申请书 return ans;
}
int main()
{int N;while(scanf("%d%d",&N,&T)==2&&N&&T){for(int i=0;i<=N;i++) sons[i].clear();for(int i=1;i<=N;i++){ int f; cin>>f;sons[f].push_back(i); //i的上司是f }cout<<dp(0)<<endl;}return 0;
}
详细解决方案
UVA 12186 Another Crisis
热度:12 发布时间:2023-09-23 09:12:11.0