## 腾讯面试题-快乐树 ### 题目描述 整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。 这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则： 1.如果某个员工来了，那么这个员工的所有直接下级都不能来。 2.派对的整体快乐值是所有到场员工快乐值的累加。 3.你的目标是让派对的整体快乐值尽量大。 给定一棵多叉树，请输出派对的最大快乐值。 ### 代码实现 ```cpp #include <iostream> #include <vector> #include <memory> using namespace std; struct HappyTree { typedef shared_ptr<HappyTree> ptr; int happy; vector<HappyTree::ptr> datas; HappyTree(int h) : happy(h) {} ~HappyTree() { datas.clear(); } void addEmploee(HappyTree::ptr e) { datas.push_back(e); } }; int maxHappy(HappyTree* root, bool canBeyondRoot) { int happyNoRoot = 0; for (auto x : root->datas) { happyNoRoot += maxHappy(x.get(), true); } int happyWithRoot = 0; if (canBeyondRoot) { happyWithRoot += root->happy; for (auto x : root->datas) { happyWithRoot += maxHappy(x.get(), false); } } return max(happyNoRoot, happyWithRoot); } int main(int argc, char** argv) { HappyTree::ptr h1 = make_shared<HappyTree>(1); HappyTree::ptr h2 = make_shared<HappyTree>(2); HappyTree::ptr h3 = make_shared<HappyTree>(3); HappyTree::ptr h4 = make_shared<HappyTree>(4); HappyTree::ptr h5 = make_shared<HappyTree>(5); HappyTree::ptr h6 = make_shared<HappyTree>(6); HappyTree::ptr h7 = make_shared<HappyTree>(7); h2->addEmploee(h5); h3->addEmploee(h6); h4->addEmploee(h7); h1->addEmploee(h2); h1->addEmploee(h3); h1->addEmploee(h4); int happy = maxHappy(h1.get(), true); cout << "happy=" << happy << endl; return 0; } ``` ### 进程和线程 进程是系统进行资源分配和调度的基本独立单位 线程是进程的一个实体，是CPU调度和分派的基本单位 多进程和多线程在执行过程中都需要一定的同步机制进行同步 系统开销：进程在创建和切换的开销远大线程，但进程相比线程更健壮（因为进程之间相互独立）