当前位置: 首页 > 工具软件 > Titan > 使用案例 >

ural 1917. Titan Ruins: Deadly Accuracy(Titan Ruins系列)

西门高歌
2023-12-01

链接:http://acm.timus.ru/problem.aspx?space=1&num=1917

描述:

间限制:1秒

空间限制:64MB

你去一个洞窟内探险,洞窟内有许多宝石,但都有魔法守护,你需要用魔法将它们打下来。

每个宝石都有自己的防御等级,当你的魔法超过它的防御等级时它就会被你打下来。

但是,当它被你打下来的时候,它会反弹你的魔法。如果反弹的魔法过强,你就会被自己的魔法杀死。

很不幸的是,你的魔法是群体性的,你不能选择攻击谁,只要防御等级低于你魔法水平的宝石都会被你打下来。并且每个都会反弹你的魔法。

你可以假设你的魔法水平无限大,但你躲避反弹的魔法的能力却并不是很强。

输入:

第一行两个数,分别是:N,宝石总数。P:你躲避反弹魔法的能力。(只要达到这个数你就会死)

第二行N个数,每个宝石的防御等级。

输出:

一行,两个数,分别是你能打下多少宝石,以及需要释放几次魔法。

样例输入:

5 4

4 1 4 1 2

样例输出:

3 2

样例说明:

第一次用强度为1的魔法打下两个防御等级为1的宝石,反弹魔法为2,可以承受。

第二次用强度为2的魔法打下一个防御等级为2的宝石,反弹魔法为2,可以承受。

剩余2个防御等级为4的宝石,是无法打下来的。(反弹魔法会达到8)

所以答案为3 2.

再附上几组数据:

5 4

2 2 1 1 1

5 2

5 7

4 1 4 1 2

3 1

思路:直接按照题意模拟就行了。

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <functional>
 5 #include <algorithm>
 6 using namespace std;
 7 int n, p;
 8 int count(int *a, int val)                              //统计大小为val的spell可以打掉多少宝石
 9 {
10     int num = 0;
11     for (int i = 0; i < n; ++i)
12         if (a[i] <= val && a[i] != 0)
13             ++num;
14     return num;
15 }
16 void asign(int *a, int val)                           //将已经被打掉的置零
17 {
18      for (int i = 0; i < n; ++i)
19          if (a[i] <= val)      
20             a[i] = 0;
21 }
22 int main()
23 {
24     while (scanf("%d %d", &n, &p)!= EOF)
25     {
26     int a[n];
27     for (int i = 0; i < n; ++i)
28         scanf("%d", &a[i]);
29     std::sort(a, a + n, greater<int>());               //要求咒语数尽可能小,所以从大到小排序
30     int sum = 0, magic_num = 0;                           //sum是打下的宝石数量,magicn是魔法数
31     int t = -1;                                        //t作为一个标记,当sum数不再增加时,sum==t,模拟结束
32     while (1)
33     {
34             
35         for (int i = 0; i < n; ++i)
36         {
37             int cnt = count(a, a[i]);
38             if (a[i] != 0 && a[i] * cnt <= p)           //小于等于p,不是小于
39             {
40                 sum += cnt;
41                 asign(a, a[i]);
42                 ++magic_num;
43             }
44                 while (a[i] == a[i+1] && i < n)        //跳过相同的a[i]
45                     ++i;
46         }
47         if (t == sum)                                  //结束标记,t是记录上次的sum用的,上下两次相同模拟结束
48            break;
49         t = sum;
50     }
51     printf("%d %d\n", sum, magicn);
52 }
53    // system("pause");
54     return 0;
55 }

代码写的有点乱。上面这个代码好像不能直接复制,下面是ac的代码。就比上面的少了注释。

//g++ 4.7.2 提交
#include <iostream>
#include <cstdio>
#include <cstring>
#include <functional>
#include <algorithm>
using namespace std;
int n, p;
int count(int *a, int val)
{
	int num = 0;
	for (int i = 0; i < n; ++i)
		if (a[i] <= val && a[i] != 0)
			++num;
	return num;
}
void asign(int *a, int val)
{
	for (int i = 0; i < n; ++i)
		if (a[i] <= val)
			a[i] = 0;
}
int main()
{
	while (scanf("%d %d", &n, &p)!= EOF)
	{
		int a[n];
		for (int i = 0; i < n; ++i)
			scanf("%d", &a[i]);
		std::sort(a, a + n, greater<int>());
		int sum = 0, magicn = 0;
		int t = -1;
		while (1)
		{
			for (int i = 0; i < n; ++i)
			{
				int cnt = count(a, a[i]);
				if (a[i] != 0 && a[i] * cnt <= p)
				{
					sum += cnt;
					asign(a, a[i]);
					++magicn;
				}
				while (a[i] == a[i+1] && i < n)
					++i;
			}
			if (t == sum)
				break;
			t = sum;
		}
		printf("%d %d\n", sum, magicn);
	}
	return 0;
}



 类似资料: