1822. Hugo II’s War
Time limit: 0.5 secondMemory limit: 64 MB
The glorious King Hugo II has declared a war—a war that is holy, victorious, almost bloodless, but ruinous!
Right after declaring the war the king has started summoning the army. He plans to send a recruitment order to all his immediate vassals, who will send the order to their vassals, and so on. In the end, every nobleman of the kingdom will be involved in the preparation for the war.
As soon as a nobleman who has no vassals receives the order, he immediately begins recruiting soldiers and joins his overlord in a few days. If a nobleman has vassals, he waits until there are at leastx% of his immediate vassals ready for the war, then summons his own troops and also joins his overlord. The glorious King Hugo II will go the war as soon as at leastx% of his immediate vassals are ready.
King Hugo II wants to state the numberxin his recruitment order. The king needs as many soldiers as possible for his military campaign. However, if the recruitment takes more thantdays, the enemy may learn about the imminent intrusion and strike first. Help Hugo II find the maximal possible value ofx.
Input
The first line contains the numbernof noblemen in the kingdom and the maximal number of daystthat can be spent for summoning the army (1 ≤n≤ 104; 0 ≤t≤ 106). The noblemen are numbered from 1 ton. King Hugo II has number 1, and the noblemen with numbers from 2 tonare described in the followingn 1 lines. Thei-th of these lines describes the nobleman with numberiand contains integerspiandti, wherepiis the number of his overlord andtiis the number of days thei-th nobleman will need to summon his troops (1 ≤pi≤n; 0 ≤ti≤ 100).
Output
Output the maximal possible value ofxwith absolute error at most 104.
Sample
inputoutput
6 31 22 22 11 21 450.00000000
题意：
输入 n 个人，3是表示有多少时间让编号1 的人召集人马。
然后按2到n 的编号 输入pi 和ti。分别是那个人直接 领主，和召集自己本部的人所需的时间。 编号1 是大领主 。 假设 每个领主都只能在 直属下属 有≥x% 的人召齐了人马才可以开始招自己的人。 问x最大是多少，可以让大领主在 t 的时间内 召齐自己的人出发打仗。
做法：
二分x，判断下这个x能否在所需时间内召齐人马。
#include <stdio.h>#include <stdlib.h>#include <string.h> #include <string>#include <iostream>#include <algorithm>using namespace std; #include <vector> long long p[10010],t[10010];long long nowt[10010];long long pai[100010];double x;long long sum_t;vector <long long >son[10010];void dfs(long long nod){if(son[nod].size()==0){nowt[nod]=t[nod];return ;}for(long long i=0;i<son[nod].size();i++) dfs(son[nod][i]); long long need=ceil(1.0*son[nod].size()*x/100.0);//找到所需的最少人数是多少for(long long i=0;i<son[nod].size();i++) pai[i]=nowt[son[nod][i]];sort(pai,pai+son[nod].size());long long ret;if(need==0)ret=0;elseret=pai[need-1]; //手下的人中，，花费最长时间的那个人nowt[nod]=ret+t[nod];}long long deal(){dfs(1); if(nowt[1]>sum_t)return 0;elsereturn 1;}int main(){ long long n;while(scanf("%I64d%I64d",&n,&sum_t)!=EOF){for(long long i=1;i<=n;i++)son[i].clear();for(long long i=2;i<=n;i++){scanf("%I64d%I64d",p+i,t+i);son[p[i]].push_back(i);}double l=0,r=100;//double mid;while(abs(r-l)>0.0001){mid=(l+r)/2.0;x=mid;if(deal()==0)//所需时间大于 sum_tr=mid;elsel=mid;} printf("%.7lf\n",l); }return 0;}
我只愿，在你的理想和希望里能为你增加一点鼓励，
