首页 > 代码库 > UVALive 3664:Guess(贪心 Grade E)
UVALive 3664:Guess(贪心 Grade E)
vj题目链接
题意：
有n （n<16345）个人，每个人有三个数（小于1000且最多两位小数点），表示答对对应题的得分。规定总分越高的人rank越高。总分相同，id小的rank高。现在知道rank，问这个rank是否可能，如果可能，那么rank最小的那个人的最大得分是多少。
思路：
3个数，最多8种情况。然后从rank小往上推，每次选择一个最小的能符合条件的分数，当作这个人的分数。如果能推下去，则ok，否则，不能。
坑点：
精度很坑。转成整数才过了。
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 20000struct Man{ int a[3]; int possible[8]; void read() { for (int i = 0; i < 3; i++) { double tmp; scanf("%lf", &tmp); a[i] = (int)((tmp+1e-4)*100); } for (int i = 0; i < 8; i++) { int sum = 0; for (int j = 0; j < 3; j++) { if ((i>>j)&1) { sum += a[j]; } } possible[i] = sum; } sort(possible, possible+8); }}man[N];int rk[N];int n;bool dfs(int pre, int id) { if (id <= 0) return true; int minres = 0x3f3f3f3f; bool isok = false; for (int i = 7; i >= 0; i--) { if (man[rk[id]].possible[i] > pre || (man[rk[id]].possible[i] == pre && rk[id] < rk[id+1])) { isok = true; minres = min(minres, man[rk[id]].possible[i]); } else break; } if (!isok) return false; return dfs(minres, id-1);}int main() { int cas = 1; while (scanf("%d", &n)!=EOF) { if (n == 0) break; printf("Case %d: ", cas++); for (int i = 1; i <= n; i++) { man[i].read(); } for (int i = 1; i <= n; i++) { scanf("%d",&rk[i]); } int ans = -1; for (int i = 0; i < 8; i++) { if (dfs(man[rk[n]].possible[i], n-1)) { ans = max(ans, man[rk[n]].possible[i]); } else break; } if (ans == -1) { puts("No solution"); } else { printf("%.2f\n", ans/100.0); } } return 0;}
UVALive 3664:Guess(贪心 Grade E)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。