首页 > 代码库 > codeforces 492C. Vanya and Exams 解题报告
codeforces 492C. Vanya and Exams 解题报告
题目链接:http://codeforces.com/problemset/problem/492/C
题目意思:给出 3 个整数:n, r, avg。然后有 n 行,每行有两个数:第 i 行有 ai 和 bi。表示如果写 bi 篇文章那么可以在 ai 这个分数上增加 1 分。可以增加好多次,但是前提是加完得到的分数不能超过 r。要使得 n 个exam 的分数平均分至少达到avg时需要写的最少文章是多少篇。
解决方法很简单,贪心即可。
我们当然希望写的文章越少越好,所以先对文章从小到大排序。然后尽量往这个exam的分数加分,直到到达上限 r 。最后的情况是不需要到达 r 时,就把剩余的加上即可,就是代码中的else 循环的:ans += need * exam[i].b;
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 typedef __int64 LL; 9 const int maxn = 1e5 + 5;10 struct node11 {12 LL a, b;13 }exam[maxn];14 15 LL cmp(node x, node y)16 {17 if (x.b == y.b)18 return x.a < y.a;19 return x.b < y.b;20 }21 22 int main()23 {24 #ifndef ONLINE_JUDGE25 freopen("in.txt", "r", stdin);26 #endif // ONLINE_JUDGE27 LL n, r, avg;28 LL has, need, needed;29 30 while (scanf("%I64d%I64d%I64d", &n, &r, &avg) != EOF)31 {32 has = 0;33 for (__int64 i = 0; i < n; i++)34 {35 scanf("%I64d%I64d", &exam[i].a, &exam[i].b);36 has += exam[i].a;37 }38 39 sort(exam, exam+n, cmp);40 LL needed = 1ll * avg * n;41 LL need = 1ll*needed - 1ll*has;42 if (need <= 0)43 printf("0\n");44 else45 {46 LL ans = 0;47 for (LL i = 0; i < n && need > 0; i++)48 {49 if ((r-exam[i].a) <= need)50 {51 ans += (r-exam[i].a) * exam[i].b;52 need -= r-exam[i].a;53 }54 else55 {56 ans += need * exam[i].b;57 need -= need;58 }59 }60 printf("%I64d\n", ans);61 }62 }63 return 0;64 }
codeforces 492C. Vanya and Exams 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。