首页 > 代码库 > UVA - 1612 Guess (猜名次)(贪心)
UVA - 1612 Guess (猜名次)(贪心)
题意:有n(n<=16384)位选手参加编程比赛。比赛有3道题目,每个选手的每道题目都有一个评测之前的预得分(这个分数和选手提交程序的时间相关,提交得越早,预得分越大)。接下来是系统测试。如果某道题目未通过测试,则该题的实际得分为0分,否则得分等于预得分。得分相同的选手,ID小的排在前面。
已知所有人的预得分,以及最终的排名,问这个排名是否可能存在,若存在,输出最后一名的最高可能得分;否则,输出No solution。每个预得分均为小于1000的非负实数,最多保留两位小数。
分析:
1、因为要保证最后一名的最高可能总分最高,所以排名在前面的人每次递减的分要尽可能少,排名第一的人分数自然不用减少。
2、如果分数与前一个名次的人相同,但是ID比前一个名次的人大,那就没必要减少总分。
3、如果分数本来就比前一个名次的人低,也没必要减少总分。
4、如果不满足条件2和3,那么就需要减少分数,假设一个人三个题目预得分为a,b,c,那么可能减少的分数是a,b,c,a+b,a+c,b+c,a+b+c,排序后,尽可能少的减少分数。
注意如果ID比前一个名次的人大,那么减少到与前一个名次的人总分相同时即可;否则,要减少到比前一个名次的人的总分小。
#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) ((a < b) ? a : b) #define Max(a, b) ((a < b) ? b : a) typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 16384 + 10; const int MAXT = 10000 + 10; inline int dcmp(double a, double b) { if(fabs(a - b) < eps) return 0; return a < b ? -1 : 1; } using namespace std; struct Node{ double a, b, c, tot; double sum[10]; void read(){ scanf("%lf%lf%lf", &a, &b, &c); tot = a + b + c; sum[0] = a; sum[1] = b; sum[2] = c; sum[3] = a + b; sum[4] = b + c; sum[5] = a + c; sum[6] = a + b + c; sort(sum, sum + 7); } }num[MAXN]; int a[MAXN]; int main(){ int n; int kase = 0; while(scanf("%d", &n) == 1){ if(!n) return 0; for(int i = 0; i < n; ++i){ num[i].read(); } for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); } printf("Case %d: ", ++kase); if(n <= 0){ printf("No solution\n"); continue; } bool flag = true; for(int i = 0; i < n; ++i){ if(!i) continue; else if(dcmp(num[a[i] - 1].tot, num[a[i - 1] - 1].tot) == 0){ if(a[i] > a[i - 1]) continue; } else if(dcmp(num[a[i] - 1].tot, num[a[i - 1] - 1].tot) == -1) continue; bool ok = false; for(int j = 0; j < 7; ++j){ if(dcmp(num[a[i] - 1].tot - num[a[i] - 1].sum[j], num[a[i - 1] - 1].tot) == -1 || (dcmp(num[a[i] - 1].tot - num[a[i] - 1].sum[j], num[a[i - 1] - 1].tot) == 0 && a[i] > a[i - 1])){ num[a[i] - 1].tot -= num[a[i] - 1].sum[j]; ok = true; break; } } if(!ok){ flag = false; break; } } if(!flag){ printf("No solution\n"); } else{ printf("%.2lf\n", num[a[n - 1] - 1].tot); } } return 0; }
UVA - 1612 Guess (猜名次)(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。