103010.打怪兽
难度普及+/提高
内存256MB
时间3000ms
题目描述
在一款电脑游戏中，你需要打败
只怪物（从 1到 n编号）。
为了打败第 i
只怪物，你需要消耗 d(i)
点生命值，但怪物死后会掉落血药，使你恢复 a(i)
点生命值。
任何时候你的生命值都不能降到
（0或 以下）。
请问是否存在一种打怪顺序，使得你可以打完这
只怪物而不死掉。
输入格式
第一行两个整数 n,z
，分别表示怪物的数量和你的初始生命值。
接下来
n行，每行两个整数 d(i) a(i)
。
输出格式
第一行为 TAK（是）或 NIE（否），表示是否存在这样的顺序。
如果第一行为 TAK，则第二行为空格隔开的
的排列，表示合法的顺序。
输入输出测试点
输入 #1
复制
3 5
3 1
4 8
8 3
输出 #1
复制
TAK
2 3 1
贪心算法，我们先根据它打败这个怪兽后，是收益还是亏损，分为两个数组，我这里用了一个pair数组，pair数组里面存两个数字，分别为亏损的，和idx（因为最后要输出编号），同时用一个数组存一下每组收益的，然后将pair两个数组排序，收益的数组，按照first从小到大，亏损的，按照从大到小。
```c++
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
typedef pair<ll,ll> pii;
pii b[N],c[N];
ll a[N];
ll cnt1=0,cnt2=0;
ll cmp(pii x,pii y)
{
return x.first>y.first;
}
int main() {
ll n,z;
cin>>n>>z;
for(int i=0; i<n; i++) {
ll x;
cin>>x>>a[i];
if(a[i]>=x) {
b[cnt1++]= {x,i};
} else {
c[cnt2++]= {x,i};
}
}
sort(b,b+cnt1);
sort(c,c+cnt2,cmp);
int flag=0;
for(int i=0; i<cnt1; i++) {
ll x=b[i].first,idx=b[i].second,y=a[idx];
if(z>=x) {
z=z+y-x;
} else {
flag=1;
break;
}
}
if(flag==0) {
for(int i=0; i<cnt2; i++) {
ll x=c[i].first,idx=c[i].second,y=a[idx];
if(z>=x) {
z=z+y-x;
} else {
flag=1;
break;
}
}
}
if(flag==1) {
puts("NIE");
} else {
puts("TAK");
for(int i=0; i<cnt1; i++)
cout<<b[i].second+1<<" ";
for(int i=0; i<cnt2; i++)
cout<<c[i].second+1<<" ";
}
}
/*
3 5
3 1
4 8
8 3
*/
```
【以下回答由 GPT 生成】
解决方案: 这个问题可以通过深度优先搜索（DFS）来解决。我们可以定义一个递归函数dfs来遍历所有可能的打怪顺序。
首先，我们需要一个visited数组来记录每个怪物是否已经被访问过。初始时，所有怪物的状态都是未访问的。
然后，我们需要一个order数组来记录打怪的顺序。初始时，order数组是空的。
接下来，我们可以编写一段递归函数dfs来尝试每个怪物作为下一个要打的怪物。在函数dfs内部，我们首先检查当前生命值是否小于等于0，如果是，说明这个打怪顺序不可行。然后，我们检查是否所有怪物都已经访问完，如果是，说明这个打怪顺序是可行的，我们可以输出结果。
如果当前生命值大于0且还有未访问的怪物，我们就遍历所有未访问的怪物，分别尝试将它们作为下一个要打的怪物，并更新生命值。然后递归调用dfs函数，继续探索下一个怪物。如果在递归调用中找到了可行的打怪顺序，我们就返回true，否则，我们将当前怪物的状态设置为未访问，继续尝试其他未访问的怪物。
最后，在主函数中，我们调用dfs函数，输出结果。
以下是具体的代码实现:
#include <iostream>
#include <vector>
using namespace std;
vector<int> order; // 保存打怪的顺序
vector<int> visited; // 是否已访问标记
vector<pair<int, int>> monsters; // 怪物信息
int health; // 初始生命值
bool dfs(int cur_health) {
// 判断是否所有怪物都已访问
bool all_visited = true;
for (int i = 0; i < visited.size(); i++) {
if (visited[i] == 0) {
all_visited = false;
break;
}
}
if (all_visited) {
return true;
}
// 逐个尝试剩余未访问的怪物
for (int i = 0; i < monsters.size(); i++) {
if (visited[i] == 0 && cur_health > 0) {
visited[i] = 1; // 标记当前怪物已访问
order.push_back(i + 1); // 记录打怪顺序
int restore = monsters[i].second; // 当前怪物掉落的血药
int required_health = monsters[i].first; // 当前怪物需要消耗的生命值
cur_health = cur_health - required_health + restore; // 更新剩余生命值
if (dfs(cur_health)) {
return true;
}
// 当前怪物无法使游戏成功，回退操作
visited[i] = 0;
order.pop_back();
cur_health = cur_health + required_health - restore;
}
}
return false;
}
int main() {
int n, initial_health;
cin >> n >> initial_health;
health = initial_health;
visited.resize(n, 0);
monsters.resize(n);
for (int i = 0; i < n; i++) {
cin >> monsters[i].first >> monsters[i].second;
}
if (dfs(health)) {
cout << "TAK" << endl;
for (int i = 0; i < order.size(); i++) {
cout << order[i] << " ";
}
cout << endl;
} else {
cout << "NIE" << endl;
}
return 0;
}
输入：
3 5
3 1
4 8
8 3
输出：
TAK
2 3 1
这个算法的时间复杂度为O(n!)，其中n为怪物的数量。这是因为在每一步中，我们都需要尝试剩余未访问的怪物。对于每个未访问的怪物，我们都需要递归调用一次dfs函数。因此，总共的调用次数为n!。
【相关推荐】