当前位置: 代码迷 >> 综合 >> UVA 12186 Another Crisis
  详细解决方案

UVA 12186 Another Crisis

热度:12   发布时间:2023-09-23 09:12:11.0
#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;
}