hiho一下第189周《小P的强力值》题目分析

0
0

《小P的强力值》题目分析

令P = ΠAi^(1/Bi)

两边取log有:log(P) = Σlog(Ai)/Bi

显然log(P)越大P也越大。

观察log(P)我们可以发现

1)每种属性的收益是独立的。也就是说,当我选择第i种属性+1时,收益只与当前的Ai(当前Ai是指初始Ai+已经分配给i属性的能力点)和Bi有关,与其他属性无关。

2)每种属性内部是收益递减的。也就是说,对于第i种属性,我们第一次+1时,收益比第二次+1时大;第二次比第三次收益大。

所以我们可以用贪心策略来分配能力值。每次分配给当前提升最大的属性即可。

1 answer(s)

0

90分,求赐教

double a[11], b[11]; int n, k; double cal(int pos) { double result = 0; for (int i = 0; i < k; i++) { result += log(i == pos ? a[i] + 1 : a[i]) / b[i]; } return exp(result); }

int main() {

double ans = 0;
cin >> n >> k;
for (int i = 0; i < k; i++) {
    cin >> a[i];
}
for (int i = 0; i < k; i++) {
    cin >> b[i];
}
for (int i = 0; i < n; i++) {
    double max = 0;
    int pos = 0;
    for (int j = 0; j < k; j++) {
        double cu = cal(j);
        if (cu > max||j==0) {
            max = cu;
            pos = j;
        }
    }
    a[pos]+=1;
    ans = max;
}
cout << ans << endl;
return 0;

}

  • 估计是又有log又有除法又有累加又有exp导致精度问题 反正都暴力算了,cal改成这样就更直接 double cal(int pos) { double result = 1; for (int i = 0; i < k; i++) { result *= pow((i == pos ? a[i] + 1 : a[i]),(1.0 / b[i])); } return result; }

  • cout默认精度90分,调高一点就好,末尾没有换行会拿0分

  • 明明精度只要千分之一以内就行了 不设精度90分 保留3位40分 保留4位60分 保留5位70分 保留10位100分

  • 我是用double,输出的时候%.2lf就90/100,%.3lf就AC了,不需要4、5甚至10位啊

  • 果然,加上fixed就过了,谢谢各位大佬

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享