首页 > 代码库 > UVa 12186 Another Crisis
UVa 12186 Another Crisis
题意：
给出一个树状关系图，公司里只有一个老板编号为0，其他人员从1开始编号。除了老板，每个人都有一个直接上司，没有下属的员工成为工人。
工人们想写一份加工资的请愿书，只有当不少于员工的所有下属的T%人递交请愿书后，该员工才会将请愿书递交给他的直接上级。输出能递交到老板处，最少需要多少工人写请愿书
分析：
d(u)表示让u给上级发信最少需要多少个工人。假设u有k个子节点，则至少需要c = (k*T - 1) / 100 + 1 个直接下级发信给他才行。把所有子节点的d从小到大排序，前c个和就是d(u)。而所求答案就是d(0)。
这里考虑到浮点误差，所以才将 k*T / 100 写为 (k*T - 1) / 100 + 1 ， 这样一来c就是 不少于k的T%的最小整数。
这个递归函数写的妙，认真学习下。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 100000 + 10; 9 vector<int> sons[maxn];10 int T, N;11 12 int dp(int u)13 {14 if(sons[u].empty()) return 1;15 int k = sons[u].size();16 vector<int> d;17 for(int i = 0; i < k; ++i)18 d.push_back(dp(sons[u][i]));19 sort(d.begin(), d.end());20 int c = (k * T - 1) / 100 + 1;21 int ans = 0;22 for(int i = 0; i < c; ++i) ans += d[i];23 return ans;24 }25 26 int main(void)27 {28 #ifdef LOCAL29 freopen("12186in.txt", "r", stdin);30 #endif31 32 while(scanf("%d%d", &N, &T) == 2)33 {34 if(!N && !T) break;35 36 for(int i = 0; i <= N; ++i)37 sons[i].clear(); 38 for(int i = 1; i <= N; ++i)39 {40 int x;41 scanf("%d", &x);42 sons[x].push_back(i);43 }44 printf("%d\n", dp(0));45 }46 47 return 0;48 }
UVa 12186 Another Crisis
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。