Codeforces 1132 E
题意:给\(cnt_i\)个\(i\)(\(1\leq i\leq 8\)),问用这些数所能构成的最大的不超过\(W\)的数。
思路:随机+贪心。。。
我们考虑将贪心和一个奇奇怪怪的随机算法结合在一起取最大值。
贪心:我们枚举所有的\(8\)个数的排列,然后将第\(i\)个数尽量取到能取的最大值,加入答案。
-
随机:首先我们考虑约束条件\(t\)。\(t\)从\(1\)开始,然后逐步收敛为\(t\times0.999999\),\(t\times0.999999^2\)、。。。
然后我们随机地考虑一个数\(i\),再看如果当前的数超过了\(w\),那么我们肯定要将\(i\)取的个数压下去,则随机\([0,nowchosen_i\times t]\)中的一个作为新的\(i\)取的个数。否则我们需要将\(i\)取的个数加上去,则随机\(nowchosen_i+[0,(cnt_i-nowchosen_i)\times t]\)中的一个作为新的\(i\)取的个数。
最后取这两种方法的\(max\)即可。