我找到了这个 Kattis 问题的解决方案:
https://open.kattis.com/problems/funnygames
但它使用 >?= unix 语法,我需要更改它才能在 Kattis 中编译。我分别将它们更改为 std::min 和 std::max,但我没有得到正确的答案(我每次都得到 Michael)。
原始代码:
/* Sample solution to "Funny Games" from NCPC 2005
* Algorithm: essentially continuous DP, keep track of winning intervals
* Author: Per Austrin
*/
#include <cmath>
#include <cassert>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef pair<double, double> pdd;
template <class It, class OIt>
OIt ival_union(It begin, It end, OIt dest) {
sort(begin, end);
while(begin != end) {
*dest = *begin++;
while(begin != end && begin->first < dest->second + 1e-8)
dest->second >?= begin++->second; //Change 1
++dest;
}
return dest;
}
int main(void) {
int n, k;
double x, f[10], maxf;
pdd win[10000], lose;
for (scanf("%d", &n); n--; ) {
scanf("%lf%d", &x, &k);
maxf = lose.second = 0;
for (int i = 0; i < k; ++i)
scanf("%lf", f+i), win[i] = make_pair(1, 1 / f[i]), maxf >?= f[i]; //Change 2
for (int nwin = k, l = 0; x > lose.second; ++l) {
nwin = ival_union(win + l , win + nwin, win + l) - win;
lose.second = (lose.first = win[l].second) / maxf;
if (l < nwin-1) lose.second <?= win[l+1].first; //Change 3
for (int i = 0; i < k; ++i)
win[nwin++] = make_pair(lose.first/f[i], lose.second/f[i]);
}
assert(fabs(x-lose.first) > 1e-6 && fabs(x-lose.second) > 1e-6);
printf("%s\n", x < lose.first ? "Nils" : "Mikael");
}
}
我的 3 个改变:
std::max(dest->second, begin++->second); //Change 1
scanf("%lf", f + i), win[i] = make_pair(1, 1 / f[i]), std::max(maxf, f[i]); //Change 2
if (l < nwin - 1) std::min(lose.second, win[l + 1].first); //Change 3
输入是
4
6 2 0.25 0.5
10 2 0.25 0.5
29.29 4 0.3 0.7 0.43 0.54
29.30 4 0.3 0.7 0.43 0.54
输出应该是
Mikael
Nils
Nils
Mikael
但在我得到改变之后
Mikael
Mikael
Mikael
Mikael
最佳答案
阅读评论后,我意识到我做了 max(a,b),但没有做 a=max(a,b),所以在我做出更改后它按预期工作。变化是:
dest->second=std::max(dest->second, begin++->second);
scanf("%lf", f + i), win[i] = make_pair(1, 1 / f[i]), maxf=std::max(maxf, f[i]);
if (l < nwin - 1) lose.second=std::min(lose.second, win[l + 1].first);
感谢您的帮助!
关于c++ - 如何更改 UNIX 语法以获得正确的输出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41294647/