洛谷 P11045 [蓝桥杯 2024 省 Java B] 最优分组
[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]
[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]
首先得注意这么一点： k k k 必须得是 n n n 的因数（这里的 n , k n,k n,k 对应于题目的 N , K N,K N,K），不然不合法。
其实这虽然是限制，但是这个限制其实是使得题目的难度大大降低了。因为这样每组的宠物数量相同，有完全相同的规律，不需要特殊讨论。
每组 k k k 只宠物，一共需要分成 c = n k c=\dfrac{n}{k} c=kn 组。
对于每组宠物，假设被感染的宠物数量为 x x x。调动我们残存的高中知识，我们惊喜地发现， x x x 服从二项分布。于是我们知道 E ( x ) = k p E(x)=kp E(x)=kp。
但是这并没有什么用。我们需要知道的是有宠物感染病毒的概率。正难则反，没有宠物感染病毒的概率是 p k p^{k} pk，所以有宠物感染病毒的概率就是 ( 1 − p k ) \left ( 1 - p^{k} \right ) (1−pk)。
一旦有动物感染，就需要重新进行 k k k 次测试。于是每一组测试次数的期望值是 k + k × ( 1 − p k ) k+k \times \left (1 - p^{k} \right ) k+k×(1−pk)。
一共有 c c c 组，由期望的线性可加性知，总的期望即为 n × [ k + k × ( 1 − p k ) ] n \times \left [ k + k \times \left ( 1 - p^{k} \right ) \right ] n×[k+k×(1−pk)]，化简即为 n k + n × ( 1 − p k ) nk+n \times \left ( 1 - p^{k} \right ) nk+n×(1−pk)。
一个快速幂，加上枚举即可。总时间复杂度 O ( n log n ) O(n \log n) O(nlogn)。不过这个时间复杂度好像有点问题？反正就是线性对数就对了。
另外：不要忘记特判 k = 1 k=1 k=1 的情况。 k = 1 k=1 k=1 时的检测次数就是 n n n！！！
Code \color{blue}{\text{Code}} Code
int n,ans;double p,minn;
double ksm(double u,int v){
快速幂自己写，太简单啦
}
double f(int k){
return n/k+n*(1-ksm(1-p,k));
}
int main(){
cin>>n>>p;
minn=n;ans=1;//特判 k=1
for(int i=2;i<=n;i++)
if (n%i==0){
double tmp=f(i);
if (tmp<minn){
minn=tmp;
ans=i;
}
}
printf("%d",ans);
return 0;
}
原文地址：https://blog.csdn.net/ZHUYINGYE_123456/article/details/142685445
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！