首页 > 代码库 > CodeForces Round #280 (Div.2)
CodeForces Round #280 (Div.2)
A. Vanya and Cubes
题意：
给你n个小方块，现在要搭一个金字塔，金字塔的第i层需要 个小方块，问这n个方块最多搭几层金字塔。
分析：
根据求和公式，有，按照规律直接加就行，直到超过n。
1 #include <cstdio> 2 3 int main() 4 { 5 int n; 6 scanf("%d", &n); 7 int sum = 0, cnt = 0; 8 while(n > sum) 9 {10 cnt++;11 sum += cnt * (cnt + 1) / 2;12 }13 if(sum > n) cnt--;14 printf("%d\n", cnt);15 16 return 0;17 }
B. Vanya and Lanterns
题意：
有一条长为l的路，每个灯的坐标为ai(坐标原点为路的最左端)，每个路灯照亮的范围为d，要求整条路都能被照亮，求d的最小值。
分析：
上来写个了二分，果断超时了。
换个思路：
对这n个路灯的位置排序
因为d要照亮整条路，所以要满足：
- 第一个路灯要照亮路的最左端，d至少为 a0
- 两个相邻路灯之间要被照亮，d至少为(ai - ai-1) / 2
- 最后一个路灯要照亮路的最右端，d至少为 l - an-1
要同时满足这些条件，取其中最大值即可。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int maxn = 1000 + 10; 5 double a[maxn], l; 6 int n; 7 8 int main() 9 {10 scanf("%d%lf", &n, &l);11 for(int i = 0; i < n; ++i) scanf("%lf", &a[i]);12 std::sort(a, a + n);13 14 double ans = a[0] - 0;15 for(int i = 1; i < n; ++i)16 {17 ans = std::max(ans, (a[i]-a[i-1])/2);18 }19 ans = std::max(ans, l - a[n-1]);20 printf("%.10f\n", ans);21 22 return 0;23 }
C. Vanya and Exams(贪心)
题意：
有n门科目满分为r，每门科目现有分数为ai，每提高该科目一分需要写bi篇文章。为了要使平均分不低于avg，求写文章的最少篇数。
分析：
很明显的贪心，计算出一个还需要提高的分数，在不超过满分的前提下先提高bi小的科目的分数。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int maxn = 100000 + 10; 5 6 typedef __int64 LL; 7 8 struct Exam 9 {10 LL a, b;11 Exam(LL a=0, LL b=0):a(a), b(b) {}12 bool operator < (const Exam& rhs) const13 {14 return b < rhs.b;15 }16 }exam[maxn];17 18 int main()19 {20 LL n, r, avg, sum = 0;21 scanf("%I64d%I64d%I64d", &n, &r, &avg);22 for(int i = 0; i < n; ++i)23 {24 LL a, b;25 scanf("%I64d%I64d", &a, &b);26 sum += a;27 exam[i] = Exam(a, b);28 }29 std::sort(exam, exam + n);30 31 LL ans = 0, p = 0;32 LL need = n * avg - sum;33 while(need > 0)34 {35 if(exam[p].a == r) { p++; continue; }36 LL temp = std::min(need, r - exam[p].a);37 ans += temp * exam[p].b;38 need -= temp;39 p++;40 }41 printf("%I64d\n", ans);42 43 return 0;44 }
D. Vanya and Computer Game(数论)
题意：
题意没弄清，结果无限WA
有两个人每次对怪物造成1点伤害，怪物的血量为a。
他们两人的每秒攻击次数分别为x、y，而且攻击时间均匀分布在这1秒内
问打败该怪物时，是被谁打败的，还是同时被两个人打败的。
分析：
首先我们化小数为整数，不妨将1秒均匀分成xy份单位时间
则两人分别每隔y、x个单位时间攻击一次，对怪物造成1点伤害
我们得到两人每次攻击时间的序列
y, 2y, 3y,,,,,,
x, 2x, 3x,,,,,,
有序合并两个序列，我们就能知道怪物是被谁打到的。
可以用一个标记数组0、1、2来记录第i次攻击是第一个人、第二个人、两人同时发起的。
不难发现其实标记数组是循环的，所以只要求出其中一个循环节即可。
循环节长度为x/g + y/g，其中g = gcd(x, y)，注意在两人同时发出攻击时，怪物是收到2点伤害的。
1 #include <cstdio> 2 3 typedef __int64 LL; 4 const int maxn = 4000000 + 10; 5 char flag[maxn]; 6 7 LL gcd(LL a, LL b) 8 { 9 LL r = a % b;10 while(r)11 {12 a = b;13 b = r;14 r = a % b;15 }16 return b;17 }18 19 int main(void)20 {21 //freopen("in.txt", "r", stdin);22 LL n, x, y;23 scanf("%I64d%I64d%I64d", &n, &x, &y);24 LL g = gcd(x, y);25 LL p = 1, q = 1, cnt = 1;26 while(p <= y/g || q <= x/g)27 {28 if(x*p < y*q)29 {30 p++;31 flag[cnt++] = 0;32 }33 else if(x*p > y*q)34 {35 q++;36 flag[cnt++] = 1;37 }38 else39 {40 p++;41 q++;42 flag[cnt++] = 2;43 }44 }45 flag[0] = flag[cnt] = 2;46 47 for(int i = 0; i < n; ++i)48 {49 LL a;50 scanf("%I64d", &a);51 a %= cnt;52 if(flag[a] == 0) puts("Vova");53 else if(flag[a] == 1) puts("Vanya");54 else puts("Both");55 }56 57 return 0;58 }
CodeForces Round #280 (Div.2)