Uva 1612 Guess

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Thinking about it:

题目要求最后一名（也就是第N位）的分数要尽量的大，那么就一定要求第N-1名的分数也要尽量大。假如N-1可以取400和500，那么N-1应该取500，如果取400，可能第N位就不能取450，而只能取350了，这样不满足要求。综上，可以从第1位开始，分数尽量取高一点，依次类推，一直取道最后。假设第N-1位的 id 为 a，第 N 位的 id 为 b，如果 a < b，那么第N位可以取与第N-1位相同的分数，否则只能取比第N-1位的分数小的而又尽量大的数（题目中有描述：If two players got the same total score, the one with the smaller ID number got a higher rank）。如果没有符合上述条件的数可以取，那么就是"No solution"。

这题有一个注意点：输入的分数是浮点数，而且最多有两个小数点。为了尽可能避免浮点数带来的误差，可以将分数*100后转化为整数处理，在输出时再除以100。

Reference:

http://acm.lilingfei.com/uva-1612-guess-%E4%B9%A0%E9%A2%988-8_104

PS:

开始处理这题时，我自信满满，因为我认为我的思路是对的。后来证明，思路确实是对的。但问题就出在浮点数处理上，而且我一直没发现这个问题，直至我查阅了大神的代码才知道处理浮点数的技巧。所以：能把浮点数转化位整数的话，就把它转化为整数处理吧。

Code:

/**
* AC @ Sep 18th 2015
* Run Time : 0.073s
*/
#include <bits/stdc++.h>using namespace std;const int MAXN = 20000 + 50;
int ord[MAXN];
std::vector<int> score[MAXN];
// count from 1
int N;void read() {
double x, y ,z;
for (int i = 1; i <= N; ++i) {
cin >> x >> y >> z;
// the operations about precision is surprisingly vital,
// especially the round function
int a = (int)round(x * 100);
int b = (int)round(y * 100);
int c = (int)round(z * 100);
// initialize the score[i] at the same time
score[i] = {0, a, b, c, a + b, a + c, b + c, a + b + c};
sort(score[i].begin(), score[i].end());
}
for (int i = 1; i <= N; ++i) {
cin >> ord[i];
}
}int find(int id, int value, int former_id) {
for (int i = (int)score[id].size() - 1; i >= 0; -- i) {
if (value == score[id][i] && id > former_id) {
return value;
} else if (value > score[id][i]) {
return score[id][i];
}
}
return -1;
}int done() {
int guess = score[ord[1]][ score[ord[1]].size() - 1 ];
for (int i = 2; i <= N; ++i) {
guess = find(ord[i], guess, ord[i - 1]);
if (guess == -1) {
return -1;
}
}
return guess;
}int Case = 0;
void work() {
read();
int ans = done();
cout << "Case " << (++Case) << ": ";
if (ans == -1) {
cout << "No solution" << endl;
} else {
cout << fixed << setprecision(2) << (ans / 100.0) << endl;
}
}int main(int argc, char const *argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> N && N) {
work();
}
return 0;
}