万户网络建一个网站虽要多少钱,互联网营销平台,棋牌游戏网站建设费用,产品营销策略包括哪些内容Problem - C - Codeforces
题意#xff1a; 思路#xff1a;
一开始想太简单wa6了
只想到先感染大的分量#xff0c;然后最后把最大的分量剩下的染色
但是可能会有别的分量更大#xff08;因为最后给最大的染色之后可能不再是最大的#xff09;
可以用堆维护#xf…Problem - C - Codeforces
题意 思路
一开始想太简单wa6了
只想到先感染大的分量然后最后把最大的分量剩下的染色
但是可能会有别的分量更大因为最后给最大的染色之后可能不再是最大的
可以用堆维护但是这里用二分做法
我们可以二分答案mid,问题就变成了mid秒内能否感染所有结点.
首先Injection一定用于优先感染兄弟结点比较多的结点,这样可以充分利用Spreading,我们可以结点按照兄弟的数量排序,然后优先感染兄弟多的结点.这样我们就知道了,第一秒被Injection的结点剩下的时间里可以被Spreading mid-1个兄弟,第二秒可以被Injection的结点可以被Spreading mid-2个兄弟,所以我们扫描一遍就可以知道还剩下多少个兄弟结点还没被感染,判断能否用剩下的Injection的操作将这些结点感染即可. Code
#include bits/stdc.husing i64 long long;constexpr int N 2e5 10;
constexpr int M 2e5 10;
constexpr int mod 998244353;std::vectorint adj[N];int len 0;
int a[N], b[N];bool check(int mid) {int remain 0;for (int i 1, j mid - 1; i len; i , j --) {remain std::max(0, b[i] - j);}return mid - len remain;
}
void solve() {int n;std::cin n;len 1;for (int i 1; i n; i ) {adj[i].clear();b[i] 0;}b[0] 1;for (int i 2; i n; i ) {int x;std::cin x;adj[x].push_back(i);}for (int i 1; i n; i ) {if (adj[i].size()) {b[len] adj[i].size() - 1;}}std::sort(b 1, b 1 len, std::greaterint());int ans 0;int l 1, r 1e9;while(l r) {int mid l r 1;if (check(mid)) {ans mid;r mid - 1;}else {l mid 1;}}std::cout ans \n;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;std::cin t;while(t --) {solve();}return 0;
}
