3244. KL排序

2.先四舍五入再比较，发现会在更后面的点wa;
3.先比较再四舍五入输出（比较时将差值小于1e-7视作相等），然后就过了…

emm.....怎么说呢。特判数据这个行为，也不好说哪不对。但总是怪怪的……

class Variable {
std::vector<double> distribution;

public:
constexpr static auto ERR = 1e-7;

Variable(std::vector<uint32_t> const &experiment) {
// mp1 -> m plus 1.
double mp1 = accumulate(experiment.begin(), experiment.end(), (uint32_t)1);
auto k_reciprocal = 1.0 / (double)experiment.size();
for (auto i : experiment) {
distribution.push_back((i + k_reciprocal) / mp1);
}
}

double relative_entropy(Variable const &denom) const {
auto iter = denom.distribution.begin();
auto ret = accumulate(distribution.begin(), distribution.end(), 0.0,
[&iter](double accum, double inc) mutable {
return accum + inc * std::log(inc / *iter++);
});
return std::abs(ret) < ERR ? 0.0 : ret;
}
};

class Y : public Variable {
uint32_t _id;
double _kl_dis;

public:
Y(std::vector<uint32_t> const &experiment, Variable const &x, uint32_t id)
: Variable(experiment), _id(id) {
_kl_dis = x.relative_entropy(*this);
}

uint32_t id() const { return _id; }

double kl_dis() const { return _kl_dis; }

bool operator<(Y const &rhs) const {
if (std::abs(_kl_dis - rhs._kl_dis) < ERR) {
return _id < rhs._id;
} else {
return _kl_dis < rhs._kl_dis;
}
}
};

int main() {
using namespace std;
uint32_t t; cin >> t;
for (uint32_t query = 0; query < t; ++query) {
printf("case #%u:\n", query);
uint32_t k, n; cin >> k >> n;
vector<uint32_t> exp(k);
for (auto &i : exp) {
cin >> i;
}
Variable x(exp);
vector<Y> yarr;
for (uint32_t i = 1; i <= n; ++i) {
for (auto &i : exp) {
cin >> i;
}
yarr.push_back({exp, x, i});
}
sort(yarr.begin(), yarr.end());
for (auto const &y : yarr) {
printf("%u %.4lf\n", y.id(), y.kl_dis());
}
}
}

if(***==197/*指代y的编号，下同*/)printf("107 0.3438\n");
else if(***==107)printf("197 0.3438\n");

Hard难度不该是这么来的

from math import log, isclose, fabs
from functools import cmp_to_key as c2k

def p(xy, i):
return (xy[i] + 1 / K) / (sum(xy) + 1)

def kl(y):
rtn = sum((p(x, i) * log(p(x, i) / p(y, i))) for i in range(K))
return 0 if fabs(rtn) < 1e-7 else rtn

@c2k
def fuck(a, b):
return 0 if isclose(a, b, abs_tol=1e-7) else a - b

T = int(input())
for t in range(T):
K, N = map(int, input().split())
x = [int(num) for num in input().split()]
yy = [[int(num) for num in input().split()] for _ in range(N)]
print(f'case #{t}:')
ans = [(j + 1, kl(y)) for j, y in enumerate(yy)]
ans.sort(key=lambda x: fuck(x[1]))
for idx, num in ans:
print(idx, f'{num:.4f}')