服务器上怎么搭建网站,营销型网站推广服务,wordpress 开发 知乎,深圳营销型网站设计公司C-连环爆炸_第四届辽宁省大学生程序设计竞赛#xff08;正式赛#xff09;#xff08;重现赛#xff09;兴安真人 (nowcoder.com)
链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空…C-连环爆炸_第四届辽宁省大学生程序设计竞赛正式赛重现赛兴安真人 (nowcoder.com)
链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld
题目描述
星穹铁道启动 希儿打怪对面是n个自爆怪。每个怪有ai和bi两个参数ai代表这个怪物的血量bi代表这个怪物身亡后自爆对所有单体怪物造成的伤害。 你可以选择任意怪物进行“手动消灭”将其血量变为0。 当一个怪物由于“手动消灭”或其他怪物的自爆血量变为0及0以下则该怪物被消灭并对所有单体怪物造成bi的伤害。 问最少“手动消灭”几个怪物能消灭所有怪物。 注意这些怪是可以通过怪的自爆连续引爆的。
输入描述:
第一行一个正整数n表示怪物的数量。接下来的n行每行两个正整数ai和bi。ai代表这个怪物的血量bi代表这个怪物身亡后自爆对所有单体怪物造成的伤害1≤n≤40001≤ai≤10000000001≤bi≤250000
输出描述:
输出一个正整数表示能消灭所有怪物的最少使用“手动消灭”的次数。
示例1
输入
复制5 4 2 6 2 7 2 8 2 10 2
5
4 2
6 2
7 2
8 2
10 2
输出
复制2
2
示例2
输入
复制5 4 2 6 2 7 100 8 2 10 2
5
4 2
6 2
7 100
8 2
10 2
输出
复制1
1
解析 1.首先想明白杀怪的最优解。需要筛选出一定不能被炸死的怪即所有怪爆炸伤害之和减去该怪的爆炸伤害该怪的生命值手动将它杀死积累伤害值。这一步非常重要 2.剩余的都是可以被炸死的怪可以放心地按爆炸伤害从高到低的顺序杀注意伤害相等时先杀生命值高的每杀一个积累伤害值需要找到目前伤害可以炸死的怪物因此想到还需要一个按生命值从小到大排序的数据结构。可以知道此时怪物死到哪里了不需要死一个怪再判断其他的怪物是否有被炸死的。 #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing namespace std;
typedef long long LL;
const int N 4e3 5;
int n;
struct node {LL a, b;int flg 0;
}arr[N];int cmp(const struct node a, const struct node b) {if (a.b b.b)return a.a b.a;return a.b b.b;
}int main() {cin n;LL num 0;for (int i 1; i n; i) {scanf(%lld%lld, arr[i].a, arr[i].b);num arr[i].b;}sort(arr 1, arr 1 n, cmp);LL sum 0,cnt0;int ff 0;for (int i 1; i n; i) {if (num - arr[i].b arr[i].a) {sum arr[i].b;arr[i].flg 1;cnt;}}ff 1;for (int i 1; i n; i) {//cout cnt endl;while (ff) {ff 0;for (int j n; j 0; j--) {if (arr[j].a sum arr[j].flg 0) {sum arr[j].b;arr[j].flg 1;ff 1;}}}if (arr[i].flg 0) {arr[i].flg 1;sum arr[i].b;cnt;ff 1;}}cout cnt endl;return 0;
}
队列版
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing namespace std;
typedef long long LL;
const int N 4e3 5;
int n;
LL s[N][2],fg[N];
struct ss {int index;LL a, b;bool operator (const ss t)const {if (b t.b)return a t.a;return b t.b;}
};struct ll {int index;LL a, b;bool operator(const ll t)const {return a t.a;}
};priority_queuessq1;
priority_queuellq2;int main() {cin n;int sum 0;for (int i 1; i n; i) {scanf(%lld%lld,s[i][0],s[i][1]);sum s[i][1];}int cnt 0, su 0;for (int i 1; i n; i) {fg[i] 1;}for (int i 1; i n; i) {if (sum - s[i][1] s[i][0]) {su s[i][1];cnt;fg[i] 0;}else {q1.push({ i,s[i][0],s[i][1] });q2.push({ i,s[i][0],s[i][1] });}}while (!q1.empty() !q2.empty()) {while (!q2.empty()suq2.top().a) {if(fg[q2.top().index])su q2.top().b;fg[q2.top().index] 0;q2.pop();}if (q2.empty())break;while (!q1.empty()fg[q1.top().index]0) {q1.pop();}if (q1.empty())break;cnt;su q1.top().b;fg[q1.top().index] 0;q1.pop();}cout cnt endl;return 0;
}
