關心員工(25)
Description
SLF是G市某集團的總裁,他認為能一起打拼的員工都是好兄弟,是以他十分關心公司各個層次員工的生活水準。在公司中,每位員工都有且隻有一名直屬上司(SLF除外),而上司有可能有多個下屬員工,于是各級員工之間就有了層次之分。為了更好地給員工補貼,SLF會定期統計各層次員工的平均收入。由于SLF忙于處理集團事務,于是想請你幫忙程式設計解決這個問題。
Input
K N_1 N_2 ... N_K SalaryK N1 N2 ... NK Salary輸入第一行中給出一個整數N(1 \leq N \leq 10^5)N(1≤N≤105),即整個公司的總人數,每個員工從1到N編号,總裁SLF的編号為1。随後N行,第i行給出編号為i的員工的相關資訊,格式如下:
K N_1 N_2 ... N_K SalaryK N1 N2 ... NK Salary
其中K是一個整數(0 \leq K \leq20)(0≤K≤20),表示該員工直接下屬員工的個數,N_iNi是直接下屬員工的編号,Salary是一個正數(Salary \leq 2*10^4)(Salary≤2∗104),表示該員工的收入。
Output
在一行中對應輸出公司的層次數m,随後m行中輸出各層次員工的平均工資,格式為”Level i: average_iaveragei”(不含雙引号),其中average_iaveragei表示第i層員工的平均工資,需要保留兩位小數。
Sample Input 1
7
2 2 3 100
3 4 5 6 2
1 7 3
0 4
0 5
0 6
0 7
Sample Output 1
3
Level 1: 100.00
Level 2: 2.50
Level 3: 5.50
看這個題目時已經晚了。在20分以上的題,這道25分的題起碼有些想法。特麼我看着不會的題在那瞎想什麼,不會基本上再糾結也是浪費時間。賽後敲了一下代碼。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100005;
const int maxdepth=100005; // 大小不确定,交了幾次,發現要這麼大才能AC
vector<int> g[maxn];
double w[maxn];
double sum[maxdepth];
int cnt[maxdepth];
int depth=-1;
int n;
// dfs(1, 1)
void dfs(int r, int level)
{
sum[level]+=w[r];
cnt[level]++;
if(level>depth)
depth=level;
for(int i=0;i<g[r].size();i++)
dfs(g[r][i], level+1);
}
int main()
{
cin>>n;
int i, j;
for(i=1;i<=n;i++)
{
int cnt, t;
cin>>cnt;
for(j=0;j<cnt;j++)
{
cin>>t;
g[i].push_back(t);
}
cin>>w[i];
}
dfs(1, 1);
printf("%d\n", depth);
for(i=1;i<=depth;i++)
printf("Level %d: %.2lf\n", i, sum[i]/cnt[i]);
return 0;
}